c# - 查找具有数百万个元素的两个列表或哈希集之间的公共元素数量

Question

在 c# 中，有哪些高效的方法可以确定两个列表或哈希集之间的公共元素数量，这些列表或哈希集可能有数百万个值？

score 7 · Accepted Answer

HashSets 将提供最佳性能。您可以使用IntersectWith方法。

// assuming HashSet<T> hashSetA
//     and an IEnumerable<T> collectionB
hashSetA.IntersectWith(collectionB);

基于哈希集的解决方案提供了 O(n) 的性能，这几乎是它所能得到的。

下一个最好的方法是对两个列表进行排序，然后在两个列表上锁定步长线性迭代，选择公共元素，这会产生 O(nlogn) 性能。

score 1 · Accepted Answer

HashSet 相交

为了比较两个列表，我将创建较大的 HashSet

score 0 · Accepted Answer

0

使用除

于 2013-03-28T20:01:50.313 回答

3 回答 3