HashSet<int> 和 List<int> 的快速交集

Question

我有一个 HashSet<int> 和一个 List<int>（哈希集大约有 300 万个项目，列表大约有 30 万个项目）。

我目前使用

与它们相交

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

我想知道是否有更快的方法。也许并行？

Answer 1

是的，你可以走得更快，因为你已经有了HashSet。 LINQ Intersect uses a generic algorithm，本质上是每次调用时从头开始重新创建一个 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();

我不希望它会更快，如果有的话，因为工作量是 too granular。调用 lambda 300,000 次的开销可能会掩盖并行性的任何好处。

结果的顺序也不会保留，除非在查询中添加 AsOrdered PLINQ 方法，进一步损害操作的性能。

Answer 2

将大量整数存储为紧凑位集而不是 HashSet 或 List 可能会更快（至少如果您使用 List像 HashSet 一样存储唯一的整数）。从这个意义上说，有几种选择：

内置BitArray stores each bit in a compact way. As an example, if you're storing integers from 1 through 65000, BitArray requires about 8125 bytes of memory (as opposed to 65000 bytes if each bit were stored as an 8-bit byte). However, BitArray may not be very memory-efficient if the highest set bit is very large (e.g., 3 billion), or if the set of bits is sparse (there are huge areas with set bits and/or clear bits). You can intersect two BitArrays using the Xor方法
压缩位集同样以紧凑的方式存储每个位，但也会压缩自身的一部分以进一步节省内存，同时仍然保持集合操作（如交集）的效率。示例包括 Elias-Fano 编码、Roaring Bitmaps 和 EWAH。请参阅 graphs 在性能和内存方面比较压缩位集与未压缩 (FixedBitSet) 的不同实现（请注意，它们比较 Java 实现，但它们在 .NET 中可能仍然有用例）。

Answer 3

HashSet 有一个方法 IntersectWith that is optimized if intersection is performed between two hash sets。使用方法 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) performance of your original method (Linq Intersect), methods proposed by @TheodorZoulias (）和我的方法（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     |
------------------------------------------------------------------------

从table我们可以看出，最快的方法是HashSet Contains Parallel，最慢的是Linq Intersect。

这是用来衡量性能的 complete source code。

HashSet<int> 和 List<int> 的快速交集

Fast intersection of HashSet<int> and List<int>

c#

algorithm

performance

intersection

hashset