c# - HashSet 和 List 的快速交集

Question

我有一个 HashSet<int>和一个 List<int> (Hashset 大约有 300 万个项目，List 大约有 300k 个项目)。

我目前使用它们相交

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

我想知道是否有更快的方法来做到这一点。也许并行？

Answer 1

HashSet有一个方法 IntersectWith 即 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 )您的原始方法( Linq Intersect )、@TheodorZoulias 提出的方法( HashSet Contains and 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 .

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