寻找两个 ICollection<T> 集合中是否包含相同对象的最快方法

Question

什么是查找两个ICollection<T>集合是否包含完全相同的条目的最快方法？暴力破解很明显，我想知道是否有更优雅的方法。

我们使用的是C# 2.0，因此请尽可能不要使用扩展方法！

编辑：对于有序和无序的集合，答案都很有趣，希望每个答案都不同。

- Joel in G&#246;

---

那么是追求速度还是优雅？它们两者并不相容。 - nawfal

Answer 1

首先比较集合的Count，如果它们具有相同的计数，则对所有元素进行暴力比较。最坏情况下是O(n)。这是在元素顺序需要相同的情况下。

第二种情况是顺序不同的情况下，您需要使用字典来存储集合中找到的元素的计数：以下是可能的算法

• 比较集合计数：如果它们不同则返回false
• 迭代第一个集合
  • 如果字典中不存在该项，则添加一个键为Item，值为1（计数）的条目
  • 如果存在该项，则增加字典中该项的计数；
• 迭代第二个集合
  • 如果该项不在字典中，则返回false
  • 如果该项在字典中，则减少该项的计数
    • 如果计数== 0，则删除该项；
• return Dictionary.Count == 0;

- Pop Catalin

Answer 2

使用C5

http://www.itu.dk/research/c5/

ContainsAll

检查提供的集合中的所有项是否在此包中（计算重复项）。要查找的项。如果找到所有项，则为True。

[Tested]

public virtual bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : T
{
  HashBag<T> res = new HashBag<T>(itemequalityComparer);

  foreach (T item in items)
    if (res.ContainsCount(item) < ContainsCount(item))
      res.Add(item);
    else
      return false;

  return true;
}

- Clueless

---

好的，我猜ContainsCount使用哈希进行查找，所以查找是O(1)，因此总体时间复杂度为O(n) - 虽然如果“this”包含一个子集，则它将返回true... - Chris Kimpton

Answer 3

对于有序集合，您可以使用由System.Linq.Enumerable定义的SequenceEqual()扩展方法：

if (firstCollection.SequenceEqual(secondCollection))

- Kent Boogaart

Answer 4

你是指相同的条目还是按相同顺序的相同条目？

无论如何，假设您想比较它们是否以相同顺序包含相同的条目，在C# 2.0中“暴力破解”确实是您唯一的选择。我知道你所说的不太优雅，但如果原子比较本身是O(1)，整个过程应该是O(N)，这并不是那么糟糕。

- DrJokepu

Answer 5

如果条目需要按相同顺序（除了相同之外）排列，则建议作为优化同时迭代两个集合并比较每个集合中的当前条目。否则，暴力搜索是可行的方法。

哦，还有另一个建议-您可以覆盖集合类的Equals并在其中实现相等性内容（取决于您的项目）。

- Dan C.

Answer 6

再次使用C5库，有两个集合，您可以使用：

C5.ICollection<T> set1 = C5.ICollection<T> ();
C5.ICollection<T> set2 = C5.ICollecton<T> ();
if (set1.UnsequencedEquals (set2)) {
  // 做一些事情
}

C5库包括一个启发式算法，实际上首先测试两个集合的无序哈希码（请参见C5.ICollection<T>.GetUnsequencedHashCode()），因此如果两个集合的哈希码不相等，则不需要迭代每个项以测试相等性。

还要注意的是，C5.ICollection<T>继承自System.Collections.Generic.ICollection<T>，因此您可以在仍然使用.NET接口的同时使用C5实现（尽管通过.NET的吝啬接口访问的功能较少）。

- Marcus Griep

Answer 7

暴力破解需要O(n) - 比较所有元素（假设它们已排序），我认为这是你能做的最好的事情 - 除非数据具有某些属性使其更容易。

我想对于未排序的情况，它的时间复杂度是O(n*n)。

在这种情况下，我认为基于归并排序的解决方案可能会有所帮助。

例如，您是否可以重新设计它，使只有一个集合？或者3个集合，一个用于仅在集合A中的元素，一个用于仅在B中的元素，另一个用于两者都在的元素 - 因此，如果仅在A和B中的元素为空，则它们相同...我可能完全走错了方向...

- Chris Kimpton