Как я могу быстро определить, содержит ли список список?

Question

Есть несколько связанных вопросов, но я ищу решение, специфичное для моего случая.Существует массив (обычно) 14 целых чисел, каждое в диапазоне от 1 до 34. Как я могу быстро определить, присутствует ли хотя бы один int в определенном статическом списке хотя бы один раз в этом массиве?

Для справкиВ настоящее время я использую этот код, который был написан так, чтобы максимально приблизиться к спецификации, поэтому его можно значительно улучшить:

if (array.Count < 13) {
    return;
}

var required = new int[] {
    0*9 + 1,
    0*9 + 9,
    1*9 + 1,
    1*9 + 9,
    2*9 + 1,
    2*9 + 9,                
    3*9 + 1,
    3*9 + 2,
    3*9 + 3,
    3*9 + 4,
    3*9 + 5,
    3*9 + 6,
    3*9 + 7,
};

IsThirteenOrphans = !required.Except (array).Any ();

Требуемый список не является динамическим, то есть он всегда будетто же самое во время выполнения.Использование Linq необязательно, основным аспектом является производительность.

Редактировать:

• Входной массив не отсортирован.
• Входные значения могутпоявляются несколько раз.
• Входной массив будет содержать не менее 14 элементов, т.е. на 1 больше, чем требуемый массив.
• Существует только 1 обязательный массив, и он статический.
• Необходимые значения различны.
• Вы можете предположить, что создание гистограммы дешево.

Обновление: Меня также интересует решение дляотсортированный входной массив.

Answer 1

Одна из возможностей - изменить способ хранения данных.Поскольку диапазон возможных значений ограничен 1-34, вместо хранения списка чисел вы можете хранить счетчики каждого присутствующего числа:

int[] counts = new int[34];

Если в вашем списке есть одна 1 и две 3,затем считает [0] == 1 && counts [2] = 2 (вы можете поочередно использовать индексирование на основе 1, если это ускоряет процесс (меньше вычитаний.))

Теперь оценим, что каждое int в спискепоявляется по крайней мере один раз, вы просто индексируете в массив последовательно для каждого x и проверяете, что все счетчики [x]> 0. Будут накладные расходы, связанные с преобразованием данных из формы count в форму списка, но это только проблема, еслиВам также часто нужно просматривать данные в виде списка.Другое преимущество этого формата хранения заключается в том, что добавление / удаление к счетчикам никогда не будет включать более одного элемента массива;в форме списка удаление элемента в середине списка влечет за собой копию нескольких элементов.

Answer 2

Это выглядит как хороший кандидат для побитовых операций, поскольку требуемые значения различны, статичны и находятся в диапазоне от 1 до 34. Вместо сохранения в виде массива сохраните его как const ulong. В ваших массивах для проверки создайте новый ulong, заполненный смещением влево каждого значения и поразрядным или.

const ulong comparator = (1UL << 1) | (1UL << 9) | (1UL << 10) | (1UL << 18) | (1UL << 19) | (1UL << 27) | (1UL << 28) | (1UL << 29) | (1UL << 30) | (1UL << 31) | (1UL << 32) | (1UL << 33) | (1UL << 34);

public static bool ContainsDistinct13Values(int[] array)
{
    ulong word = 0;
    foreach (int i in array)
    {
        word |= (1UL << i);
    }
    return word == comparator;
}

Answer 3

Если у вас есть 34+-битный целочисленный тип и битовые операции в стиле C, то вы можете вычислить такое целое число V из списка переменных (если список v [0], v [1], ...тогда V равен (1 << v [0]) | (1 << v [1]) ..., где 1 того же типа, что и V), и имеет предварительно определенное целое число S для статического списка, вычисляемого аналогично.Тест, чтобы увидеть, содержится ли статический список в списке переменных, равен (S & ~ V) == 0. </p>

Answer 4

Если вы хотите быстрый способ, вам не следует использовать linq. Если для заданного списка все ниже 35, вы можете удалить if (lst[i] < 35) Ниже приведен список обхода ответов не более одного раза, который действует как counting sort:

public bool FindExactMatch(int[] array, List<int> lst)
{
    bool[] a34 = new bool[35];

    foreach(var item in array)
    {
        a34[item] = true;
    }

    int exact = 0;

    for (int i = 0; i < lst.Count; i++)
    {
        if (a34[lst[i]])
        {
            exact++;
            if (exact == array.Length) return true;

            a34[lst[i]] = false;
        }
    }

    return false;
}

для отсортированного списка, если размер списка велик, вы можете сделать lst.BinarySearch(array[i]), что занимает максимум 14 * log (n) * c1, и я думаю, что это будет достаточно эффективно, даже если вы реализуете егоможет стать быстрее, и я не тестировал бинарный поиск с моей собственной реализацией, но Min, Max, Sort в linq медленнее (между 4 и 10 раз) вашей собственной (хорошей) реализации.И если размер отсортированного списка мал, я предпочитаю использовать алгоритм, как указано выше, потому что константа c1 мала в приведенном выше алгоритме и может быть больше в алгоритме двоичного поиска.

Answer 5

Идея 1
Если вам нужно сравнить несколько списков required, вы можете отсортировать входной список, а затем просто сравнить его путем итерации. Но сортировка, конечно, не слишком быстрая, но и не слишком медленная. Но если вы сравните с несколькими обязательными списками, накладные расходы на сортировку могут быстро амортизироваться.

После сортировки массива сравнение становится тривиальным:

for(int i = 0; i < 14; i++)
  if(arr[i] != required[i]) return false;

return true;

Идея 2
Или, если 14 целых чисел различны / уникальны, вы можете просто сделать required HashSet и сделать

input.Count(i => required.Contains(i)) == 14

Но я не знаю, фактически не проверив, если это быстрее, чем сортировка.

Идея 3
Вычислите быстрый хеш, который является инвариантным для перестановок в течение 14 дюймов, и сравните его с известным значением require. Только в случае совпадения хешей более дорогое сравнение.

//Prepare/precalculated
int[] hashes = new int[34];
Random random = new Random();
for(int i = 0; i < 34; i++)
  hashes[i] = random.NextInt();

//On each list
int HashInts(int[] ints)
{
  int result = 0;
  foreach(int i in ints)
    result += hashes[i - 1];

  return result;
}

Мудрый выбор значений для hashes может немного улучшить его, но случайные значения должны быть в порядке.

Идея 4
Создайте гистограмму:

int[] CreateHistogram(int[] ints)
{
  int[] counts = new int[34];
  foreach(int i in ints)
  {
    counts[i - 1]++;
  }

  return counts;
}

Вы можете избежать создания массива, повторно используя существующий массив, если производительность действительно важна.

Answer 6

Редактировать: Итак, я понял ваш вопрос и, возможно, у меня есть какое-то приятное, слишком сложное решение.Другой вопрос, насколько хорошая производительность у него.

static void Main(string[] args)
{
    var required = new int[]
                       {
                           0*9 + 1,
                           0*9 + 9,
                           1*9 + 1,
                           1*9 + 9,
                           2*9 + 1,
                           2*9 + 9,
                           3*9 + 1,
                           3*9 + 2,
                           3*9 + 3,
                           3*9 + 4,
                           3*9 + 5,
                           3*9 + 6,
                           3*9 + 7,
                       };

    precomputed = required.Select((x, i) => new { Value = x, Offset = (UInt16)(1 << i) }).ToDictionary(x => x.Value, x => x.Offset);

    for (int i = 0; i < required.Length; i++)
    {
        precomputedResult |= (UInt16)(1 << i);
    }

    int[] array = new int[34]; // your array goes here..
    Console.WriteLine(ContainsList(array));

    Console.ReadKey();
}

// precompute dictionary
private static Dictionary<int, UInt16> precomputed;
// precomputed result
private static UInt16 precomputedResult = 0;

public static bool ContainsList(int[] values)
{
    UInt16 result = 0;
    for (int i = 0; i < values.Length; i++)
    {
        UInt16 v;
        if (precomputed.TryGetValue(values[i], out v))
            result |= v;
    }

    return result == precomputedResult;
}

Answer 7

Вы можете легко пройтись по предметам и выяснить, не пропало ли их.По вашему примеру я понимаю, что вы просто хотели узнать, отсутствует ли какой-либо элемент из требуемого в массиве.так что вы можете написать

bool notContains = false;

foreach (var iddd in required)
{
    foreach (var ar in array)
    {
        if (iddd == ar) notContains=true;
    }

    if (notContains == false) break;
}

Это намного быстрее, чем ваш подход.Проверьте код ниже с добавленным таймером.Ваш подход занял 5 мс, а новый - 0 мс

System.Diagnostics.Stopwatch aTimer = new System.Diagnostics.Stopwatch();
aTimer.Start();

var IsThirteenOrphans = !required.Except(array).Any();
aTimer.Stop();

System.Diagnostics.Stopwatch bTimer = new System.Diagnostics.Stopwatch();
bTimer.Start();
bool notContains = false;

foreach (var iddd in required)
{
    foreach (var ar in array)
    {
        if (iddd == ar) notContains=true;            
    }

    if (notContains == false) break;
}

bTimer.Stop();