0

我猜它没有，但如果有人可以确认。

如果我尝试相交两组：A（100 万项）B（1 项）

框架是否总是执行 A.Contains(B) 一次，而不是 B.Contains(A) 一百万次？

这是假设相交是如何在引擎盖下工作的，这与我不知道的一些花哨的算法相反。

更新：

好的，所以对于 c# 你应该清楚地这样做B.InsersectWith(A)，如果 B << A.Intersect()被定义IEnumerable并且根据下面的答案（和 MSDN）效率会低很多。因此，如果您使用最佳工具（即IntersectWith().

4

3 回答 3

3

从文档

如果另一个参数表示的集合是与当前 HashSet 对象具有相同相等比较器的 HashSet 集合，则该方法是 O(n) 操作。否则，此方法是 O(n + m) 操作，其中 n 是 Count，m 是 other 中的元素数。

HashSet.IntersectWith 方法

如果您正在寻找速度实现（覆盖）GetHashCode，如果您可以从您的数据中派生出有意义的哈希。并覆盖 Equal。我对将在集合中的任何类执行此操作。

Object.GetHashCode 方法

于 2012-09-07T14:40:41.457 回答
0

这取决于您是作为一般问题还是针对特定语言提出问题。

在 Java 中，它将遍历第二个集合，然后遍历第一个集合以查看它是否包含该元素。所以它仍然会遍历这两个集合。

在c#中，该方法的作用是枚举第一个集合（A）的元素，然后枚举第二个集合（B）的元素并标记那些共同的元素，然后按该顺序生成这些元素。

所以，要回答你的问题，我会说它没有。这是它必须通过每个容器

于 2012-09-07T13:47:08.757 回答
0

代码是针对一般情况编写的。如果您是这样的特殊情况，您应该实现对您的特定用例有效的自定义逻辑。

Contains() 方法只是遍历列表，直到找到匹配项，因此如果这就是它正在做的事情，顺序肯定很重要，但我相信另一个答案就其工作方式而言是正确的，因为这意味着迭代每个item 最多一次，而“包含”解决方案可以为主列表中的每个元素迭代整个“子”列表。

实际解决方案 = x+y 次迭代 包含解决方案 = x+(x*y) 次迭代

于 2012-09-07T13:59:15.203 回答