渐近行为IEnumerable.Intersect vs HashedSet.IntersectWith

Question

我已经阅读了很多关于HashSet和LINQ Set Operations的帖子和博客,我得到的印象是linq交集方法内部使用散列集作为第一个集合,IEnumerable作为第二个集合.因此,两者之间的差异是linq交集的O(n + m),而两个散列集之间的散列集交集的O(n).我可以得到确认吗？在MSDN中没有记录LINQ交叉的大O.

Answer 1

嗯，它是特定于实现的，所以理论上它可能会改变 - 但基本上区别只是使用HashSet.IntersectWith你从一个哈希集开始，所以你只需要迭代一个集合。

“明显”的实现将分别为Intersect和提供 O(M + N) 和 O(N) 复杂度IntersectWith- 当然，假设有一个合适的哈希码。如果看到任何其他实现，我会感到非常惊讶，而且我当然没有看到任何证据表明 .NET 的任何版本都附带了除此之外的任何内容。

可以说，如果两个参数都Intersect已经存在，那么HashSet<T>您可以优化它以迭代较小的集合并检查每个元素是否在较大的集合中。然而，这有另一个问题，即集合可能不使用相同的比较器彼此或作为调用Intersect。

有关更多详细信息，请参阅我的Edulinq 实现和帖子，包括有关 MSDN 中不准确之处的注释。MSDN声称（在撰写本文时）：

当枚举此方法返回的对象时，Intersect 首先进行枚举，收集该序列的所有不同元素。然后它枚举第二个，标记在两个序列中出现的那些元素。最后，标记的元素按照它们被收集的顺序生成。

无论是在顺序还是时间上，这实际上都是不正确的：

• 它是second最初枚举的（完整地，当MoveNext()第一次在返回的序列上调用时）
• 结果是在迭代时生成的first- 它们是流式传输的，而不是 MSDN 声称的“标记所有内容然后生成结果”