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

Question

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

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

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

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

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

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

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

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

Есть ли лучший метод?

Answer 1

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

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

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

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

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

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

Answer 2

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

Тогда вам нужно только использовать полученный XOR-номер в качестве ключа для 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;
}

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

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

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

Answer 3

Реализуйте 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 4

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

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

Answer 5

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

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

Answer 6

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

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