c# - 以最优化的方式求两组的交集

Question

给定两组值，我必须找出它们之间是否有任何共同元素，即它们的交集是否为空。

哪个标准 C# 集合最适合(就性能而言)用于此目的？我知道 linq 有一个 Intersect 扩展方法来找出两个列表/数组的交集，但我的重点是 Big-O notation< 方面的性能.

如果我还必须找出两个集合的交集怎么办？

Answer 1

好吧，如果你使用 LINQ 的 Intersect方法它将建立一个 HashSet第二个序列的，然后对照它检查第一个序列的每个元素。所以它是 O(M+N)... 你可以使用 foo.Intersect(bar).Any()早点出去。

当然，如果您将一个(任一)集合存储在 HashSet<T> 中首先，您可以迭代另一个检查每个步骤的包含。不过，您仍然需要先构建集合。

从根本上说，无论您做什么，您都会遇到一个 O(M+N) 问题 - 您不会比这更便宜(总是您必须考虑的可能性每个元素)，如果你的哈希码是合理的，你应该能够轻松实现这种复杂性。当然，一些解决方案可能比其他解决方案提供更好的常数因子……但这是性能而不是复杂性；)

编辑:如评论中所述，还有 ISet<T>.Overlaps - 如果您已经设置了静态类型 ISet<T>或具体实现，调用 Overlaps让你更清楚你在做什么。如果您的两个集合都静态键入为 ISet<T> , 使用 larger.Overlaps(smaller) (就集合的大小而言，更大和更小)正如我期望的那样 Overlaps 的实现遍历参数 并根据调用它的集合的内容检查每个元素。