performance - 渐近行为 IEnumerable.Intersect 与 HashedSet.IntersectWith

Question

我读过很多关于 HashSet 和 LINQ 集操作的文章和博客，我的印象是 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 implementation and post了解更多详细信息，包括 MSDN 中有关不准确之处的注释。 MSDN claims (在撰写本文时):

When the object returned by this method is enumerated, Intersect enumerates first, collecting all distinct elements of that sequence. It then enumerates second, marking those elements that occur in both sequences. Finally, the marked elements are yielded in the order in which they were collected.

事实并非如此，无论是顺序还是时间安排:

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