Быстрое пересечение HashSet <int>и List <int> - PullRequest
Новая
       97

Быстрое пересечение HashSet <int>и List <int>

5 голосов
/ 01 мая 2020

У меня есть HashSet<int> и List<int> (в хэш-наборе приблизительно 3 миллиона элементов, в списке приблизительно 300 000 элементов).

В настоящее время я пересекаю их, используя 

var intersected = hashset.Intersect(list).ToArray();

и Интересно, есть ли более быстрый способ сделать это? Может параллельно?

Ответы [ 3 ]

3 голосов
/ 02 мая 2020

HashSet имеет метод IntersectWith, который оптимизируется на , если выполняется пересечение между двумя наборами га sh . Используя метод IntersectWith, мы можем пересечь HashSet и List, используя следующий подход: 

private static IEnumerable<int> Intersect(HashSet<int> hash, List<int> list)
{
    HashSet<int> intersect = new HashSet<int>(list);
    intersect.IntersectWith(hash);
    return intersect;
}

Я измерил (используя Stopwatch) производительность вашего оригинальный метод (Linq Intersect), методы, предложенные @TheodorZoulias (HashSet Contains и HashSet Contains Parallel) и мой метод (HashSet IntersectWith). Вот результаты: 

------------------------------------------------------------------------
|         Method            | Min, ms | Max, ms | Avg, ms | StdDev, ms |
------------------------------------------------------------------------
| Linq Intersect            |   135   |   274   |   150   |     17     |
| HashSet Contains          |    25   |    44   |    26   |      2     |
| HashSet Contains Parallel |    12   |    53   |    13   |      3     |
| HashSet IntersectWith     |    57   |    89   |    61   |      4     |
------------------------------------------------------------------------

Из таблицы видно, что самый быстрый метод - HashSet Contains Parallel, а самый медленный - Linq Intersect.

Здесь завершено исходный код , который использовался для измерения производительности.

1 голос
/ 01 мая 2020

Да, вы можете go быстрее, потому что у вас уже есть HashSet в руке. LINQ Intersect использует универсальный c алгоритм , который по сути воссоздает HashSet с нуля при каждом вызове. Вот более быстрый алгоритм: 

/// <summary>Yields all the elements of first (including duplicates) that also
/// appear in second, in the order in which they appear in first.</summary>
public static IEnumerable<TSource> Intersect<TSource>(IEnumerable<TSource> first,
    HashSet<TSource> second)
{
    foreach (TSource element in first)
    {
        if (second.Contains(element)) yield return element;
    }
}

Обновление: Вот параллельная версия вышеуказанной идеи: 

var intersected = list.AsParallel().Where(x => hashset.Contains(x)).ToArray();

Я бы не ожидал это должно быть намного быстрее, если вообще, потому что рабочая нагрузка слишком гранулированная . Затраты на вызов лямбды 300 000 раз, вероятно, затмят любые преимущества параллелизма.

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

0 голосов
/ 02 мая 2020

Возможно, вам будет проще хранить множество целых чисел в виде компактного набора битов, а не HashSet или List (по крайней мере, если вы используете List для хранения уникальных целых чисел, таких как HashSet ). В этом смысле есть несколько вариантов:

  • Встроенный BitArray сохраняет каждый бит в компактном виде. Например, если вы храните целые числа от 1 до 65000, для BitArray требуется около 8125 байтов памяти (в отличие от 65000 байтов, если каждый бит был сохранен как 8-битный байт). Однако BitArray может не очень эффективно использовать память, если максимальный установленный бит очень велик (например, 3 миллиарда), или если набор битов является разреженным (существуют огромные области с установленными битами и / или чистыми битами). Вы можете пересекать два BitArray с помощью метода Xor
  • Сжатые наборы битов также сохраняют каждый бит в компактном виде, но также сжимают части себя для дальнейшего сохранения памяти, сохраняя при этом поддержание заданных операций, таких как пересечение, эффективным. Примеры включают в себя кодирование Элиаса-Фано, Революционные растровые изображения и EWAH. См. графики , сравнивающие различные реализации сжатых битовых наборов с несжатыми (FixedBitSet) с точки зрения производительности и памяти (обратите внимание, что они сравнивают Java реализации, но они все еще могут быть полезны в. NET дело).
...