以最优化的方式交叉两组

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

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

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

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

当然,如果你在HashSet存储一个(或者一组)来开始,你可以迭代另一个检查每一步的包含。 尽管如此,你仍然需要构建集合。

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

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

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

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

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

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

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

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

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

再次根据您的情况,尽可能多地尝试找到一个规则,在这个规则中,交叉点无法避免调用它。