比较两个集合的平等性，而不考虑其中的项目顺序

我想比较两个集合（在C＃中），但我不确定实现这个效率的最好方法。

我已经阅读了关于Enumerable.SequenceEqual的另一个线程，但这并不是我正在寻找的。

就我而言，如果两个集合包含相同的项目（不pipe顺序如何），那么两个集合是相等的。

例：

collection1 = {1, 2, 3, 4}; collection2 = {2, 4, 1, 3}; collection1 == collection2; // true 

我通常做的是循环一个集合中的每个项目，看看它是否存在于其他集合中，然后遍历其他集合中的每个项目，看看它是否存在于第一个集合中。 （我通过比较长度开始）。

 if (collection1.Count != collection2.Count) return false; // the collections are not equal foreach (Item item in collection1) { if (!collection2.Contains(item)) return false; // the collections are not equal } foreach (Item item in collection2) { if (!collection1.Contains(item)) return false; // the collections are not equal } return true; // the collections are equal 

但是，这不是完全正确的，而且可能不是比较两个集合的最有效的方法。

我能想到的一个例子是错误的是：

 collection1 = {1, 2, 3, 3, 4} collection2 = {1, 2, 2, 3, 4} 

这与我的实施是一样的。 我是否应该只计算每个项目的次数，并确保两个项目的计数相等？

---

这些例子是在某种C＃中（我们称之为伪C＃），但是以你想要的任何语言给出你的答案，没关系。

注：为简单起见，我在示例中使用了整数，但是我也希望能够使用引用types的对象（它们不像键一样正确，因为只比较对象的引用，而不是内容）。

Answer 1

事实certificate，微软已经在其testing框架中涵盖了： CollectionAssert.AreEquivalent

备注

两个集合是相同的，如果它们具有相同数量的相同元素，但是以任何顺序。 如果它们的值相等，则元素是相等的，而不是如果它们指向相同的对象。

使用reflection器，我修改了AreEquivalent（）后面的代码来创build相应的相等比较器。 它比现有的答案更完整，因为它考虑了空值，实现了IEqualityComparer，并且有一些效率和边缘情况检查。 再加上，这是微软 🙂

 public class MultiSetComparer<T> : IEqualityComparer<IEnumerable<T>> { private readonly IEqualityComparer<T> m_comparer; public MultiSetComparer(IEqualityComparer<T> comparer = null) { m_comparer = comparer ?? EqualityComparer<T>.Default; } public bool Equals(IEnumerable<T> first, IEnumerable<T> second) { if (first == null) return second == null; if (second == null) return false; if (ReferenceEquals(first, second)) return true; if (first is ICollection<T> firstCollection && second is ICollection<T> secondCollection) { if (firstCollection.Count != secondCollection.Count) return false; if (firstCollection.Count == 0) return true; } return !HaveMismatchedElement(first, second); } private bool HaveMismatchedElement(IEnumerable<T> first, IEnumerable<T> second) { int firstNullCount; int secondNullCount; var firstElementCounts = GetElementCounts(first, out firstNullCount); var secondElementCounts = GetElementCounts(second, out secondNullCount); if (firstNullCount != secondNullCount || firstElementCounts.Count != secondElementCounts.Count) return true; foreach (var kvp in firstElementCounts) { var firstElementCount = kvp.Value; int secondElementCount; secondElementCounts.TryGetValue(kvp.Key, out secondElementCount); if (firstElementCount != secondElementCount) return true; } return false; } private Dictionary<T, int> GetElementCounts(IEnumerable<T> enumerable, out int nullCount) { var dictionary = new Dictionary<T, int>(m_comparer); nullCount = 0; foreach (T element in enumerable) { if (element == null) { nullCount++; } else { int num; dictionary.TryGetValue(element, out num); num++; dictionary[element] = num; } } return dictionary; } public int GetHashCode(IEnumerable<T> enumerable) { if (enumerable == null) throw new ArgumentNullException(nameof(enumerable)); int hash = 17; foreach (T val in enumerable.OrderBy(x => x)) hash = hash * 23 + (val?.GetHashCode() ?? 42); return hash; } } 

示例用法：

 var set = new HashSet<IEnumerable<int>>(new[] {new[]{1,2,3}}, new MultiSetComparer<int>()); Console.WriteLine(set.Contains(new [] {3,2,1})); //true Console.WriteLine(set.Contains(new [] {1, 2, 3, 3})); //false 

或者，如果您只是想直接比较两个集合：

 var comp = new MultiSetComparer<string>(); Console.WriteLine(comp.Equals(new[] {"a","b","c"}, new[] {"a","c","b"})); //true Console.WriteLine(comp.Equals(new[] {"a","b","c"}, new[] {"a","b"})); //false 

最后，你可以使用你select的一个相等比较器：

 var strcomp = new MultiSetComparer<string>(StringComparer.OrdinalIgnoreCase); Console.WriteLine(strcomp.Equals(new[] {"a", "b"}, new []{"B", "A"})); //true 

Answer 2

一个简单且相当有效的解决scheme是对两个集合进行sorting，然后比较它们是否相等：

 bool equal = collection1.OrderBy(i => i).SequenceEqual( collection2.OrderBy(i => i)); 

这个algorithm是O（N * logN），而你的解决scheme是O（N ^ 2）。

如果集合具有某些属性，则可以实现更快的解决scheme。 例如，如果两个集合都是哈希集合，则它们不能包含重复项目。 此外，检查一个哈希集是否包含一些元素是非常快的。 在这种情况下，类似于你的algorithm可能是最快的。

Answer 3

创build一个词典“词典”，然后为每个成员在第一个集合，做dict [member] ++;

然后，以相同的方式循环第二个集合，但是对于每个成员做dict [成员] – 。

最后，循环查看字典中的所有成员：

  private bool SetEqual (List<int> left, List<int> right) { if (left.Count != right.Count) return false; Dictionary<int, int> dict = new Dictionary<int, int>(); foreach (int member in left) { if (dict.ContainsKey(member) == false) dict[member] = 1; else dict[member]++; } foreach (int member in right) { if (dict.ContainsKey(member) == false) return false; else dict[member]--; } foreach (KeyValuePair<int, int> kvp in dict) { if (kvp.Value != 0) return false; } return true; } 

编辑：据我可以告诉这是在最有效的algorithm相同的顺序。 这个algorithm是O（N），假设Dictionary使用O（1）查找。

Answer 4

这是我的（深受D.Jennings的影响）比较方法的通用实现（在C＃中）：

 /// <summary> /// Represents a service used to compare two collections for equality. /// </summary> /// <typeparam name="T">The type of the items in the collections.</typeparam> public class CollectionComparer<T> { /// <summary> /// Compares the content of two collections for equality. /// </summary> /// <param name="foo">The first collection.</param> /// <param name="bar">The second collection.</param> /// <returns>True if both collections have the same content, false otherwise.</returns> public bool Execute(ICollection<T> foo, ICollection<T> bar) { // Declare a dictionary to count the occurence of the items in the collection Dictionary<T, int> itemCounts = new Dictionary<T,int>(); // Increase the count for each occurence of the item in the first collection foreach (T item in foo) { if (itemCounts.ContainsKey(item)) { itemCounts[item]++; } else { itemCounts[item] = 1; } } // Wrap the keys in a searchable list List<T> keys = new List<T>(itemCounts.Keys); // Decrease the count for each occurence of the item in the second collection foreach (T item in bar) { // Try to find a key for the item // The keys of a dictionary are compared by reference, so we have to // find the original key that is equivalent to the "item" // You may want to override ".Equals" to define what it means for // two "T" objects to be equal T key = keys.Find( delegate(T listKey) { return listKey.Equals(item); }); // Check if a key was found if(key != null) { itemCounts[key]--; } else { // There was no occurence of this item in the first collection, thus the collections are not equal return false; } } // The count of each item should be 0 if the contents of the collections are equal foreach (int value in itemCounts.Values) { if (value != 0) { return false; } } // The collections are equal return true; } } 

Answer 5

你可以使用一个Hashset 。 看看SetEquals方法。

Answer 6

编辑：我意识到，只要我提出这真的只适用于集 – 它不会妥善处理具有重复项目的集合。 例如，从algorithm的angular度来看，{1,1,2}和{2,2,1}将被认为是相等的。 如果你的集合是集合（或者它们的平等可以用这种方式衡量），但是，我希望你find下面的有用的东西。

我使用的解决scheme是：

 return c1.Count == c2.Count && c1.Intersect(c2).Count() == c1.Count; 

Linq做了封面下的字典，所以这也是O（N）。 （注意，如果集合的大小不同，则为O（1））。

我使用Danielbuild议的“SetEqual”方法，Igorbuild议的OrderBy / SequenceEquals方法和我的build议做了一个健全的检查。 结果如下，显示O（N * LogN）为伊戈尔和O（N）为我的和丹尼尔的。

我认为Linq交叉代码的简单性使其成为更好的解决scheme。

 __Test Latency(ms)__ N, SetEquals, OrderBy, Intersect 1024, 0, 0, 0 2048, 0, 0, 0 4096, 31.2468, 0, 0 8192, 62.4936, 0, 0 16384, 156.234, 15.6234, 0 32768, 312.468, 15.6234, 46.8702 65536, 640.5594, 46.8702, 31.2468 131072, 1312.3656, 93.7404, 203.1042 262144, 3765.2394, 187.4808, 187.4808 524288, 5718.1644, 374.9616, 406.2084 1048576, 11420.7054, 734.2998, 718.6764 2097152, 35090.1564, 1515.4698, 1484.223 

Answer 7

在没有重复和没有顺序的情况下，可以使用以下EqualityComparer来允许集合作为字典键：

 public class SetComparer<T> : IEqualityComparer<IEnumerable<T>> where T:IComparable<T> { public bool Equals(IEnumerable<T> first, IEnumerable<T> second) { if (first == second) return true; if ((first == null) || (second == null)) return false; return first.ToHashSet().SetEquals(second); } public int GetHashCode(IEnumerable<T> enumerable) { int hash = 17; foreach (T val in enumerable.OrderBy(x => x)) hash = hash * 23 + val.GetHashCode(); return hash; } } 

这是我使用的ToHashSet（）实现。 散列码algorithm来自Effective Java（通过Jon Skeet的方式）。

Answer 8

为什么不使用.Except（）

 // Create the IEnumerable data sources. string[] names1 = System.IO.File.ReadAllLines(@"../../../names1.txt"); string[] names2 = System.IO.File.ReadAllLines(@"../../../names2.txt"); // Create the query. Note that method syntax must be used here. IEnumerable<string> differenceQuery = names1.Except(names2); // Execute the query. Console.WriteLine("The following lines are in names1.txt but not names2.txt"); foreach (string s in differenceQuery) Console.WriteLine(s); 

http://msdn.microsoft.com/en-us/library/bb397894.aspx

Answer 9

 static bool SetsContainSameElements<T>(IEnumerable<T> set1, IEnumerable<T> set2) { var setXOR = new HashSet<T>(set1); setXOR.SymmetricExceptWith(set2); return (setXOR.Count == 0); } 

解决scheme需要.NET 3.5和System.Collections.Generic命名空间。 根据微软的说法 ， SymmetricExceptWith是一个O（n + m）操作， n表示第一个元素的个数， m表示第二个元素的个数。 如有必要，您可以随时将相等比较器添加到此函数。

Answer 10

埃里克森几乎是正确的：因为你想匹配重复计数，你想要一个袋子 。 在Java中，这看起来像这样：

 (new HashBag(collection1)).equals(new HashBag(collection2)) 

我确定C＃有一个内置的Set实现。 我会先用 如果性能是一个问题，你总是可以使用不同的Set实现，但使用相同的Set接口。

Answer 11

重复的sortingpost，但检查我的解决scheme比较集合 。 这很简单：

无论顺序如何，这将执行平等比较：

 var list1 = new[] { "Bill", "Bob", "Sally" }; var list2 = new[] { "Bob", "Bill", "Sally" }; bool isequal = list1.Compare(list2).IsSame; 

这将检查是否添加/删除项目：

 var list1 = new[] { "Billy", "Bob" }; var list2 = new[] { "Bob", "Sally" }; var diff = list1.Compare(list2); var onlyinlist1 = diff.Removed; //Billy var onlyinlist2 = diff.Added; //Sally var inbothlists = diff.Equal; //Bob 

这将看到字典中的项目改变：

 var original = new Dictionary<int, string>() { { 1, "a" }, { 2, "b" } }; var changed = new Dictionary<int, string>() { { 1, "aaa" }, { 2, "b" } }; var diff = original.Compare(changed, (x, y) => x.Value == y.Value, (x, y) => x.Value == y.Value); foreach (var item in diff.Different) Console.Write("{0} changed to {1}", item.Key.Value, item.Value.Value); //Will output: a changed to aaa 

原帖在这里 。

Answer 12

这个问题有很多解决scheme。 如果你不关心重复，你不必sorting。 首先确保他们有相同数量的项目。 之后，sorting其中一个集合。 然后，从已sorting的集合中的第二个集合中search每个项目。 如果你没有find一个给定的项目停止并返回false。 这样做的复杂性： – sorting第一个集合：N 日志（N） – 从第二个search每个项目到第一个：N LOG（N），所以最后以2 * N * LOG（N）查看一切。 这与sorting的复杂性相似。 如果有差异，这也给你提前停止的好处。 但是请记住，如果在进行这个比较之前都进行了sorting，并且尝试使用诸如qsort之类的东西进行sorting，sorting将会更加昂贵。 有这个优化。 另一种替代方法，对于知道元素范围的小集合来说，非常适合使用位掩码索引。 这会给你一个O（n）的performance。 另一种select是使用散列并查找它。 对于小集合，通常sorting或位掩码索引好得多。 哈希表有地方差的缺点，所以要记住这一点。 再说一遍，只有当你不在乎重复。 如果你想考虑重复与sorting两者。

Answer 13

这是我的扩展方法变种ohadsc的答案，以防某人有用

 static public class EnumerableExtensions { static public bool IsEquivalentTo<T>(this IEnumerable<T> first, IEnumerable<T> second) { if ((first == null) != (second == null)) return false; if (!object.ReferenceEquals(first, second) && (first != null)) { if (first.Count() != second.Count()) return false; if ((first.Count() != 0) && HaveMismatchedElement<T>(first, second)) return false; } return true; } private static bool HaveMismatchedElement<T>(IEnumerable<T> first, IEnumerable<T> second) { int firstCount; int secondCount; var firstElementCounts = GetElementCounts<T>(first, out firstCount); var secondElementCounts = GetElementCounts<T>(second, out secondCount); if (firstCount != secondCount) return true; foreach (var kvp in firstElementCounts) { firstCount = kvp.Value; secondElementCounts.TryGetValue(kvp.Key, out secondCount); if (firstCount != secondCount) return true; } return false; } private static Dictionary<T, int> GetElementCounts<T>(IEnumerable<T> enumerable, out int nullCount) { var dictionary = new Dictionary<T, int>(); nullCount = 0; foreach (T element in enumerable) { if (element == null) { nullCount++; } else { int num; dictionary.TryGetValue(element, out num); num++; dictionary[element] = num; } } return dictionary; } static private int GetHashCode<T>(IEnumerable<T> enumerable) { int hash = 17; foreach (T val in enumerable.OrderBy(x => x)) hash = hash * 23 + val.GetHashCode(); return hash; } } 

Answer 14

在许多情况下，唯一合适的答案是Igor Ostrovsky之一，其他答案是基于对象哈希码。 但是当你为一个对象生成一个哈希码时，你只能根据他的IMMUTABLE字段来做 – 比如对象Id字段（在数据库实体的情况下） – 为什么当Equals方法被覆盖时重写GetHashCode非常重要？

这意味着，如果比较两个集合，即使不同项目的字段不相等，结果也可能是比较方法的结果。 要深入比较集合，您需要使用Igor的方法并实现IEqualirity。

请阅读我和斯科德先生在他投票数最多的评论。

詹姆士

Answer 15

这是一个比这个改进的解决scheme。

 public static bool HasSameElementsAs<T>( this IEnumerable<T> first, IEnumerable<T> second, IEqualityComparer<T> comparer = null) { var firstMap = first .GroupBy(x => x, comparer) .ToDictionary(x => x.Key, x => x.Count(), comparer); var secondMap = second .GroupBy(x => x, comparer) .ToDictionary(x => x.Key, x => x.Count(), comparer); if (firstMap.Keys.Count != secondMap.Keys.Count) return false; if (firstMap.Keys.Any(k1 => !secondMap.ContainsKey(k1))) return false; return firstMap.Keys.All(x => firstMap[x] == secondMap[x]); } 

Answer 16

如果你使用Shouldly ，你可以使用ShouldAllBe和Contains。

 collection1 = {1, 2, 3, 4}; collection2 = {2, 4, 1, 3}; collection1.ShouldAllBe(item=>collection2.Contains(item)); // true 

最后，你可以写一个扩展名。

 public static class ShouldlyIEnumerableExtensions { public static void ShouldEquivalentTo<T>(this IEnumerable<T> list, IEnumerable<T> equivalent) { list.ShouldAllBe(l => equivalent.Contains(l)); } } 

UPDATE

ShouldBe方法存在可选参数。

 collection1.ShouldBe(collection2, ignoreOrder: true); // true