4

找出两个ICollection<T>集合是否包含完全相同的条目的最快方法是什么？蛮力很清楚，我想知道是否有更优雅的方法。

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

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

4

7 回答 7

4

使用 C5

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

包含所有

" 检查提供的集合中的所有项目是否都在这个包中
（计算多重性）。
要查找的项目。

如果找到所有项目，则为真。"

[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;
}
于 2008-11-21T11:42:07.830 回答
3

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

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

  • 比较集合计数：如果它们不同，则返回 false
  • 迭代第一个集合
    • 如果字典中不存在项目，则添加并输入 Key = Item, Value = 1（计数）
    • 如果项目存在，则增加字典中项目的计数；
  • 迭代第二个集合
    • 如果项目不在字典中，则返回 false
    • 如果项目在字典中，则项目的递减计数
      • 如果 count == 0 则删除项目；
  • 返回 Dictionary.Count == 0;
于 2008-11-21T11:38:11.563 回答
3

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

if (firstCollection.SequenceEqual(secondCollection))
于 2008-11-21T11:47:49.847 回答
2

您的意思是相同的条目或相同顺序的相同条目？

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

于 2008-11-21T11:35:15.580 回答
1

如果条目需要以相同的顺序排列（除了相同），那么我建议 - 作为一种优化 - 您同时迭代两个集合并比较每个集合中的当前条目。否则，蛮力就是要走的路。

哦，还有另一个建议——你可以为集合类重写 Equals 并在其中实现相等的东西（不过取决于你的项目）。

于 2008-11-21T11:37:18.570 回答
1

同样，使用具有两组的 C5 库，您可以使用：

C5.ICollection<T> set1 = C5.ICollection<T> ();
C5.ICollection<T> set2 = C5.ICollection<T> ();
if (set1.UnsequencedEquals (set2)) {
  // 做点什么
}

C5 库包含一个启发式算法，它首先实际测试两组的未排序哈希码（请参阅 参考资料C5.ICollection<T>.GetUnsequencedHashCode()），这样如果两组的哈希码不相等，它就不需要遍历每个项目来测试是否相等。

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

于 2009-07-10T16:44:12.517 回答
0

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

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

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

例如，您能否对其进行重新建模以使其只有一个系列？或 3 个集合，一个仅用于集合 A，一个仅用于 B，并且两者都用于 - 所以如果 A only 和 B only 是空的 - 那么它们是相同的......我可能完全走错了切线这里...

于 2008-11-21T11:31:51.607 回答