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

使用C5

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

ContainsAll

“检查是否所有项目都在 提供的收集在这个袋子里
(计算多重数)。
这个 要查找的项目。

如果所有项目均为 找到了。”

[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;
}

首先比较两种方法。 计数

第二种情况是顺序不同,您需要使用字典来存储集合中找到的元素计数:这里有一个可能的算法

• 比较集合计数:如果它们不同,则返回false
• • 如果字典中不存在项,则添加并输入Key=item,Value=1(计数)
  • 如果项目存在,则增加字典中项目的计数;
• • 如果项目不在字典中,则返回false
  • 如果项在字典中,则该项的递减计数
    • 如果计数=0,则删除项目;
• 返回字典。计数==0;

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

if (firstCollection.SequenceEqual(secondCollection))

你是说相同的条目还是相同顺序的条目?

无论如何,假设您想比较它们是否以相同的顺序包含相同的条目,“暴力”实际上是C#2.0中唯一的选项。我知道你说的不优雅是什么意思,但是如果原子比较本身是O(1),那么整个过程应该是O(N),而不是 令人不快的

哦,还有另一个建议-您可以覆盖集合类的Equals,并在其中实现equality(不过这取决于您的项目)。

同样,使用C5库,有两个集合,您可以使用:

C5.ICollection<T> set1 = C5.ICollection<T> ();
C5.ICollection<T> set2 = C5.ICollecton<T> ();
if (set1.UnsequencedEquals (set2)) {
  // Do something
}

C5库包括一个启发式程序,它首先实际测试两个集合的未排序散列码(参见 C5.ICollection<T>.GetUnsequencedHashCode()

同样值得注意的是 C5.ICollection<T> 继承自 System.Collections.Generic.ICollection<T> ,因此您可以在使用.NET接口的同时使用C5实现(尽管您可以通过.NET吝啬的接口访问较少的功能)。

暴力需要O(n)-比较所有元素(假设它们已排序),我认为这是最好的方法-除非数据的某些属性使其更容易。

我猜对于未排序的情况,它是O(n*n)。

merge sort 可能会有帮助。

例如,您是否可以对其重新建模,以便只有一个集合?或者3个集合,一个仅用于集合A中的集合,一个仅用于集合B中的集合,以及两个集合中的集合-因此,如果仅A和仅B为空-则它们是相同的。。。我可能走错了方向。。。