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

Question

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

Answer 1

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

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

基于哈希集的解决方案提供的O(n)性能几乎与它一样好.

接下来最好的方法是对两个列表进行排序,然后在两个列表中以锁定步骤线性迭代,选择公共元素,这些元素具有O(nlogn)性能.