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

Question

我有一个包含约3百万项的 HashSet<int> 和一个包含约30万项的 List<int>。

我目前使用以下方法对它们进行交集操作：

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

我想知道是否有更快的方法来完成这项任务。也许可以并行处理？

- user2033412

---

它们需要是 HashSet 和 List 吗？ - tia

Answer 1

HashSet有一个方法IntersectWith，如果在两个哈希集之间执行交集，则该方法会进行优化。使用方法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;
}

---

我使用秒表测量了您的原始方法(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。

---

这里是用于测量性能的完整源代码。

- Iliar Turdushev

Answer 2

是的，你可以更快地进行操作，因为你已经有了一个HashSet。LINQ Intersect使用一种通用算法，它在每次调用时基本上会从头开始重新创建一个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次lambda的开销可能会掩盖任何并行性的好处。

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

- Theodor Zoulias

Answer 3

如果你需要存储很多整数，相比于使用 HashSet 或 List，使用一个紧凑的位集可能会更加快速（至少在你使用 List 时需要存储唯一整数时是这样）。在这方面，有几个选择：

• 内置的BitArray以紧凑的方式存储每个位。例如，如果您要从1到65000存储整数，则BitArray需要约8125字节的存储空间（如果每个位都存储为8位字节，则需要65000字节）。但是，如果最高的设置位非常大（例如30亿），或者位的集合是稀疏的（存在大量具有设置位和/或清除位的区域），则BitArray可能不太内存效率。您可以使用Xor方法交集两个BitArray。
• 压缩位集同样以紧凑的方式存储每个位，并且还压缩它们的部分以进一步节省存储器，同时仍然保持诸如交集等设置操作的效率。例子包括Elias-Fano编码，Roaring Bitmaps和EWAH。请参见图表，比较压缩位集的不同实现与未压缩的实现（FixedBitSet）在性能和内存方面的表现（注意，它们比较Java实现，但在.NET案例中仍然可能很有用）。

- Peter O.