我已经阅读了很多关于 HashSet 和 LINQ 集操作的帖子和博客，我得到的印象是 linq 交集方法在内部使用散列集作为第一个集，而 IEnumerable 作为第二个集。所以两者之间的区别要么是 O(n + m) 用于 linq 交集，而 O(n) 用于两个散列集之间的散列集交集。我可以得到确认吗？MSDN 中没有记录 LINQ intersect 的大 O。
问问题
1112 次
1 回答
4
嗯，它是特定于实现的，所以理论上它可以改变 - 但基本上不同之处在于使用HashSet.IntersectWith你从一个哈希集开始，所以你只需要迭代一个集合。
“显而易见”的实现将分别给出 O(M + N) 和 O(N) 的复杂性Intersect-IntersectWith当然，假设一个不错的哈希码。如果看到任何其他实现，我会感到非常惊讶，而且我当然没有看到任何证据表明任何版本的 .NET 都附带了除此之外的任何东西。
可以说，如果两个参数Intersect都已经存在HashSet<T>，您可以优化它以仅迭代较小的集合并检查每个元素是否在较大的集合中。然而，这有另一个问题，即这些集合可能不会使用相同的比较器作为彼此或作为Intersect调用。
有关更多详细信息，请参阅我的Edulinq 实现并发布，包括有关 MSDN 中的不准确之处的注释。MSDN声称（在撰写本文时）：
当枚举此方法返回的对象时，Intersect 首先枚举，收集该序列的所有不同元素。然后它枚举第二个，标记出现在两个序列中的那些元素。最后，标记的元素按照它们被收集的顺序产生。
这实际上不是真的，无论是在顺序还是时间方面：
- 它
second是最初枚举的（完全MoveNext()是在返回的序列上第一次调用时） - 结果是在迭代时产生的
first——它们是流式传输的，而不是 MSDN 声称的“标记所有内容然后产生结果”
于 2013-01-28T06:52:55.963 回答