c# - 以最优化的方式交叉两个集合

Question

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

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

如果我还必须找出两组的交集呢？

Answer 1

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

当然，如果您将一个（任何一个）集合存储在 aHashSet<T>中，您可以只遍历另一个集合，检查每个步骤的包含情况。不过，您仍然需要先构建集合。

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

编辑：如评论中所述，还有ISet<T>.Overlaps- 如果您已经设置了静态类型ISet<T>或具体实现，调用Overlaps可以更清楚地说明您在做什么。如果您的两个集合都静态类型为ISet<T>，请使用larger.Overlaps(smaller)（根据集合的大小，较大和较小），因为我希望实现Overlaps迭代参数并根据您调用的集合的内容检查每个元素它在。

Answer 2

如前所述，应用Any()会给你一些性能。

我在相当大的数据集上对其进行了测试，它提高了 25%。

同样应用larger.Intersect(smaller)而不是相反非常重要，在我的情况下，它提供了 35% 的改进。

在应用 intersect 之前对列表进行排序也得到了另外 7-8%。

要记住的另一件事是，根据用例，您可以完全避免应用相交。

例如，对于整数列表，如果最大值和最小值不在同一个边界内，则不需要应用 intersect 因为它们永远不会。

对于第一个字母具有相同想法的字符串列表也是如此。

再次根据您的情况，尽可能多地尝试找到无法避免调用交集的规则。