Алгоритм для сопоставления списков целых

Question

За каждый день мы имеем около 50 000 экземпляров структуры данных (это может в конечном счете расти, чтобы быть намного больше), что инкапсулировать следующее:

DateTime AsOfDate; 
int key; 
List<int> values; // list of distinct integers 

Это, вероятно, не имеет значения, но list values - это список различных целых чисел с тем свойством, что для данного значения AsOfDate объединение values по всем значениям key создает список различных целых чисел. То есть целое число не появляется в двух разных списках values в тот же день.

Списки обычно содержат очень мало элементов (от одного до пяти), но иногда до пятидесяти элементов.

Приведенные смежные дни мы пытаемся найти экземпляры этих объектов, значения которых равны key в течение двух дней, но в списке values содержатся одинаковые целые числа.

Мы используем следующий алгоритм. Преобразование списка values в строку через

string signature = String.Join("|", values.OrderBy(n => n).ToArray()); 

затем хэш signature в целое число, порядок получившиеся списки хеш-кодов (один лист на каждый день), пройти через два списка в поисках совпадений, а затем проверить, если соответствующие ключи отличаются. (Также проверьте связанные списки, чтобы убедиться, что у нас не было хеш-коллизии.)

Есть ли лучший способ?

Answer 1

Возможно, вы просто можете просто отобразить список, а не проходить через String.

Кроме того, я думаю, что ваш алгоритм почти оптимален. Предполагая отсутствие хеш-коллизий, это O (n log n + m log m), где n и m - числа записей для каждого из двух дней, которые вы сравниваете. (Сортировка является узким местом.)

Вы можете сделать это в O (n + m), если вы используете массив ведра (по существу: хэш-таблицу), в который вы вставляете хэши. Вы можете сравнить два массива ковша в O (max (n, m)), предполагая, что длина зависит от количества записей (чтобы получить разумный коэффициент нагрузки).

Должно быть возможно, чтобы библиотека сделала это для вас (похоже, что вы используете .NET) с помощью HashSet.IntersectWith() и написания подходящей функции сравнения.

Вы не можете сделать лучше, чем O (n + m), потому что каждую запись нужно посещать хотя бы один раз.

Редактировать: неправильно, исправлено.

Answer 2

Имеет ли порядок? т. е. [1,2] в день 1 и [2,1] в день 2, равны ли они? Если они есть, то хеширование может работать не так хорошо. Вместо этого вы можете использовать отсортированный массив/вектор, чтобы помочь в сравнении.

Кроме того, какие ключи это? Имеет ли он определенный диапазон (например, 0-63)? Возможно, вы сможете объединить их в большое целое число (может потребовать точность за пределами 64-битных) и хеш вместо преобразования в строку, поскольку это может занять некоторое время.

Answer 3

В дополнение к другим ответам вы можете ускорить процесс, создав недорогой хеш, просто построенный из XOR среди всех элементов каждого Списка. Вам не нужно будет заказывать свой список, и все, что вы получите, это int, который проще и быстрее хранить, чем строки.

Тогда вам нужно всего лишь использовать полученный XORed номер в качестве ключа к Hashtable и проверить наличие ключа перед его вставкой. Если уже существует существующий ключ, только тогда вы сортируете соответствующие списки и сравниваете их.

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

Если у вас была собственная реализация List<>, вы могли бы построить генерацию ключа XOR внутри него, чтобы она была пересчитана при каждой операции в Списке.
Это позволит быстрее проверять повторяющиеся списки.

Код

Ниже первая попытка реализации этого.

Dictionary<int, List<List<int>>> checkHash = new Dictionary<int, List<List<int>>>(); 

public bool CheckDuplicate(List<int> theList) { 
    bool isIdentical = false; 
    int xorkey = 0; 
    foreach (int v in theList) xorkey ^= v; 

    List<List<int>> existingLists; 
    checkHash.TryGetValue(xorkey, out existingLists); 
    if (existingLists != null) { 
     // Already in the dictionary. Check each stored list 
     foreach (List<int> li in existingLists) { 
      isIdentical = (theList.Count == li.Count); 
      if (isIdentical) { 
       // Check all elements 
       foreach (int v in theList) { 
        if (!li.Contains(v)) { 
         isIdentical = false; 
         break; 
        } 
       } 
      } 
      if (isIdentical) break; 
     } 
    } 
    if (existingLists == null || !isIdentical) { 
     // never seen this before, add it 
     List<List<int>> newList = new List<List<int>>(); 
     newList.Add(theList); 
     checkHash.Add(xorkey, newList); 
    } 
    return isIdentical; 
} 

Не самый элегантный и легкий для чтения на первый взгляд, это скорее «hackey», и я даже не уверен, что он лучше, чем более элегантной версии от Guffa.
Что он делает, хотя заботится о столкновении в ключе XOR, сохраняя списки List<int> в словаре.

Если найден дубликат ключа, мы просматриваем каждый ранее сохраненный список до тех пор, пока не найдем несоответствие.

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

Answer 4

Внедрите IEqualityComparer для List, вы можете использовать этот список как ключ в словаре.

Если списки сортируются, это может быть так просто, как это:

IntListEqualityComparer : IEqualityComparer<List<int>> { 

    public int GetHashCode(List<int> list) { 
     int code = 0; 
     foreach (int value in list) code ^=value; 
     return code; 
    } 

    public bool Equals(List<int> list1, List<int> list2) { 
     if (list1.Count != list2.Coount) return false; 
     for (int i = 0; i < list1.Count; i++) { 
     if (list1[i] != list2[i]) return false; 
     } 
     return true; 
    } 

} 

Теперь вы можете создать словарь, который использует IEqualityComparer:

Dictionary<List<int>, YourClass> day1 = new Dictionary<List<int>, YourClass>(new IntListEqualityComparer()); 

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

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

Answer 5

Возможно, стоит разместить это в базе данных SQL. Если вы не хотите иметь полномасштабную СУБД, вы можете использовать sqlite.

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

Answer 6

Вы могли бы суммировать список значений, чтобы получить целое число, которое может использоваться как предварительный пример того, содержит ли другой список один и тот же набор значений?

Хотя будет гораздо больше столкновений (такая же сумма не обязательно означает один и тот же набор значений), но я думаю, что он может сначала сократить набор сравнений, требуемых большой частью.