问两个集合以最优化的方式相交

EN

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

当然，如果您一开始就在HashSet<T>中存储一个(任一个)集合，那么您可以只迭代另一个集合，检查每个步骤中的容纳性。不过，您仍然需要在开始时构建set。

从根本上说，无论你做什么，你都会遇到一个O(M+N)问题--你不会比这更便宜了(你总是有可能不得不查看每一个元素)，如果你的哈希码是合理的，你应该能够很容易地实现这种复杂性。当然，一些解决方案可能会比其他解决方案提供更好的恒定因子。但这是性能而不是复杂性;)

编辑:正如评论中提到的，还有ISet.Overlaps -如果你已经设置了一个静态类型的ISet<T>或一个具体的实现，调用Overlaps会让你更清楚地知道你在做什么。如果您的两个集合都静态类型化为ISet<T>，请使用larger.Overlaps(smaller) (其中较大和较小表示集合的大小)，因为我期望Overlaps的实现迭代参数，并根据调用它的集合的内容检查每个元素。

如前所述，应用Any()会给您带来一定的性能。

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

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

此外，在应用intersect之前对列表进行排序也会产生另外7-8%的结果。

另一件要记住的事情是，根据用例的不同，你可以完全避免应用intersect。

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

同样的道理也适用于字符串列表，其概念与第一个字母相同。

同样，根据您的情况，尽可能多地查找交集不可能避免调用的规则。