以最优化的方式交叉两组

Question

给定两组值,我必须找到它们之间是否存在任何共同元素,即它们的交集是否为空.

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

如果我必须找出两组的交集怎么办？

Answer 1

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

当然,如果你将一个(或者一个)设置为a HashSet<T>开头,你可以迭代另一个检查每个步骤的包含.尽管如此,你仍然需要构建集合.

从根本上说,无论你做什么都会遇到O(M + N)问题 - 你不会比那更便宜(你总是有可能需要查看每个元素)以及你的哈希码是否合理,你应该能够轻松地实现这种复杂性.当然,某些解决方案可能会提供比其他解决方案更好的常数因素...但这是性能而不是复杂性;)

编辑:正如评论中所指出的那样,ISet<T>.Overlaps如果您已经设置了静态类型ISet<T>或具体实现,那么调用Overlaps会让您更清楚自己在做什么.如果你的两个集都是静态类型的ISet<T>,则使用larger.Overlaps(smaller)(根据集合的大小越大越小),因为我希望实现Overlaps迭代参数并根据你调用的集合的内容检查每个元素它在.

Answer 2

如上所述,Apply Any()将为您提供一些性能.

我在相当大的数据集上测试了它,它提供了25%的改进.

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

在应用交叉之前对列表进行排序还有7-8%.

另外要记住的是,根据用例,您可以完全避免应用交叉.

例如,对于整数列表,如果最大值和最小值不在同一个打包程序中,则不需要应用交叉,因为它们永远不会.

对于具有应用于第一个字母的相同构思的字符串列表也是如此.

再次根据您的情况,尽可能多地尝试找到一个规则,其中交叉点是不可能避免调用的.