Сравнение двух коллекций для равенства, независимо от порядка элементов в них

Я хотел бы сравнить две коллекции (в C #), но я не уверен в том, что вы сможете эффективно реализовать это.

Я прочитал другую тему о Enumerable.SequenceEqual , но это не совсем то, что я ищу.

В моем случае две коллекции были бы равны, если бы они содержали одни и те же элементы (независимо от порядка).

Пример:

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 #), но дайте свой ответ на любом языке, который вам нужен, это не имеет значения.

Примечание. Я использовал целые числа в примерах для простоты, но хочу также использовать объекты ссылочного типа (они не ведут себя корректно как ключи, потому что сравнивается только ссылка объекта, а не контент).

Оказывается, Microsoft уже имеет это в своей тестовой структуре: CollectionAssert.AreEquivalent

замечания

Две коллекции эквивалентны, если они имеют одинаковые элементы в одном количестве, но в любом порядке. Элементы равны, если их значения равны, а не если они относятся к одному и тому же объекту.

Используя рефлектор, я изменил код позади AreEquivalent (), чтобы создать соответствующий сопоставитель сравнений. Он более полна, чем существующие ответы, поскольку он учитывает нулевые значения, реализует IEqualityComparer и имеет определенную эффективность и проверку кросс-кейсов. плюс, это Microsoft 🙂

 public class MultiSetComparer : IEqualityComparer> { private readonly IEqualityComparer m_comparer; public MultiSetComparer(IEqualityComparer comparer = null) { m_comparer = comparer ?? EqualityComparer.Default; } public bool Equals(IEnumerable first, IEnumerable second) { if (first == null) return second == null; if (second == null) return false; if (ReferenceEquals(first, second)) return true; if (first is ICollection firstCollection && second is ICollection secondCollection) { if (firstCollection.Count != secondCollection.Count) return false; if (firstCollection.Count == 0) return true; } return !HaveMismatchedElement(first, second); } private bool HaveMismatchedElement(IEnumerable first, IEnumerable 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 GetElementCounts(IEnumerable enumerable, out int nullCount) { var dictionary = new Dictionary(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 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>(new[] {new[]{1,2,3}}, new MultiSetComparer()); Console.WriteLine(set.Contains(new [] {3,2,1})); //true Console.WriteLine(set.Contains(new [] {1, 2, 3, 3})); //false 

Или, если вы просто хотите напрямую сравнить две коллекции:

 var comp = new MultiSetComparer(); 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 

Наконец, вы можете использовать свой сравнительный анализатор по вашему выбору:

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

Простым и довольно эффективным решением является сортировка обеих коллекций, а затем сравнение их для равенства:

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

Этот алгоритм O (N * logN), а ваше решение выше O (N ^ 2).

Если коллекции обладают определенными свойствами, вы можете реализовать более быстрое решение. Например, если обе ваши коллекции являются hash-наборами, они не могут содержать дубликатов. Кроме того, проверка того, содержит ли hash-набор какой-то элемент, очень быстро. В этом случае алгоритм, похожий на ваш, скорее всего, будет самым быстрым.

Создайте словарь «dict», а затем для каждого члена в первой коллекции, do dict [member] ++;

Затем, петля над второй коллекцией таким же образом, но для каждого члена do dict [member] -.

В конце зациклируйте все члены в словаре:

  private bool SetEqual (List left, List right) { if (left.Count != right.Count) return false; Dictionary dict = new Dictionary(); 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 kvp in dict) { if (kvp.Value != 0) return false; } return true; } 

Изменить: насколько я могу сказать, это тот же порядок, что и самый эффективный алгоритм. Этот алгоритм O (N), предполагая, что Словарь использует поиск O (1).

Это мое (сильно повлиянное D.Jennings) обобщенное внедрение метода сравнения (в C #):

 ///  /// Represents a service used to compare two collections for equality. ///  /// The type of the items in the collections. public class CollectionComparer { ///  /// Compares the content of two collections for equality. ///  /// The first collection. /// The second collection. /// True if both collections have the same content, false otherwise. public bool Execute(ICollection foo, ICollection bar) { // Declare a dictionary to count the occurence of the items in the collection Dictionary itemCounts = new Dictionary(); // 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 keys = new List(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; } } 

Вы можете использовать Hashset . Посмотрите на метод SetEquals .

EDIT: Я понял, как только я решил, что это действительно работает только для наборов – он не будет иметь дело с коллекциями с дублирующими элементами. Например, {1, 1, 2} и {2, 2, 1} будут считаться равными с точки зрения этого алгоритма. Однако, если ваши коллекции являются наборами (или их равенство можно измерить таким образом), я надеюсь, что вы найдете ниже полезное.

Решение, которое я использую:

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

Linq делает предмет словаря под обложками, так что это также O (N). (Обратите внимание: это O (1), если коллекции не одного размера).

Я проверил проверку работоспособности, используя метод «SetEqual», предложенный Даниэлем, метод OrderBy / SequenceEquals, предложенный Игорем, и мое предложение. Ниже приведены результаты, показывающие O (N * LogN) для Игоря и O (N) для моего и Даниэля.

Я думаю, что простота кода пересечения Linq делает его предпочтительным решением.

 __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 

В случае без повторов и без ордера, следующий EqualityComparer может использоваться, чтобы позволить коллекции как словарные ключи:

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

Здесь используется реализация ToHashSet (). Алгоритм хеш-кода исходит из эффективной Java (через Jon Skeet).

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

Для решения требуется .NET 3.5 и пространство имен System.Collections.Generic . Согласно Microsoft , SymmetricExceptWith является операцией O (n + m) , где n представляет количество элементов в первом наборе, а m – количество элементов во втором. При необходимости вы всегда можете добавить сопоставитель равенства к этой функции.

Почему бы не использовать .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 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

Повторяющийся пост, но проверьте мое решение для сравнения коллекций . Это довольно просто:

Это будет выполнять сравнение равенства независимо от порядка:

 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() { { 1, "a" }, { 2, "b" } }; var changed = new Dictionary() { { 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 

Оригинальный пост здесь .

Если вы используете 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(this IEnumerable list, IEnumerable equivalent) { list.ShouldAllBe(l => equivalent.Contains(l)); } } 

ОБНОВИТЬ

Необязательный параметр существует в методе ShouldBe .

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

erickson почти прав: поскольку вы хотите совместить с количеством дубликатов, вам нужна сумка . В Java это выглядит примерно так:

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

Я уверен, что C # имеет встроенную реализацию Set. Я бы использовал это первым; если производительность является проблемой, вы всегда можете использовать другую реализацию Set, но использовать тот же интерфейс Set.

Вот мой вариант метода расширения ответа ohadsc, если он полезен кому-то

 static public class EnumerableExtensions { static public bool IsEquivalentTo(this IEnumerable first, IEnumerable 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(first, second)) return false; } return true; } private static bool HaveMismatchedElement(IEnumerable first, IEnumerable second) { int firstCount; int secondCount; var firstElementCounts = GetElementCounts(first, out firstCount); var secondElementCounts = GetElementCounts(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 GetElementCounts(IEnumerable enumerable, out int nullCount) { var dictionary = new Dictionary(); 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(IEnumerable enumerable) { int hash = 17; foreach (T val in enumerable.OrderBy(x => x)) hash = hash * 23 + val.GetHashCode(); return hash; } } 

Вот решение, которое является улучшением по сравнению с этим .

 public static bool HasSameElementsAs( this IEnumerable first, IEnumerable second, IEqualityComparer 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]); } 

Существует много решений этой проблемы. Если вам не нужны дубликаты, вам не нужно сортировать их. Сначала убедитесь, что у них одинаковое количество элементов. После этого есть одна из коллекций. Затем binsearch каждый элемент из второго набора в отсортированной коллекции. Если вы не обнаружите, что данный пункт остановлен и возвращает false. Сложность этого: – сортировка первой коллекции: N Log (N) – поиск каждого элемента из второго в первый: N LOG (N), поэтому вы получаете 2 * N * LOG (N), считая, что они совпадают, и вы Посмотрите все. Это похоже на сложность сортировки обоих. Кроме того, это дает вам преимущество остановиться раньше, если есть разница. Однако имейте в виду, что если оба они отсортированы до того, как вы перейдете на это сравнение, и попробуйте сортировать, используя что-то вроде qsort, сортировка будет дороже. Для этого есть оптимизация. Другая альтернатива, которая отлично подходит для небольших коллекций, где вы знаете диапазон элементов, – это использовать индекс битовой маски. Это даст вам производительность O (n). Другой вариант – использовать hash и посмотреть его. Для небольших коллекций обычно намного лучше выполнять сортировку или индекс битовой маски. Hashtable имеет недостаток в худшем месте, поэтому имейте это в виду. Опять же, это только если вам не нужны дубликаты. Если вы хотите учитывать дубликаты, перейдите к сортировке обоих.

Во многих случаях единственным подходящим ответом является Игорь Островский, другие ответы основаны на хеш-коде объектов. Но когда вы создаете hash-код для объекта, вы делаете это только на основе его полей IMMUTABLE, таких как поле идентификатора объекта (в случае объекта базы данных). Почему важно переопределить GetHashCode, когда метод Equals переопределен?

Это означает, что если вы сравниваете две коллекции, результат может быть правдой для метода сравнения, даже если поля разных элементов не равны. Для глубокого сравнения коллекций вам необходимо использовать метод Игоря и реализовать IEqualirity.

Пожалуйста, прочитайте комментарии меня и господина Шнидера на его самом голосовавшем посту.

Джеймс

Разрешить дубликаты в IEnumerable (если набор нежелателен \ возможно) и “игнорировать порядок”, вы должны иметь возможность использовать .GroupBy() .

Я не специалист по измерениям сложности, но мое рудиментарное понимание заключается в том, что это должно быть O (n). Я понимаю O (n ^ 2) как результат выполнения операции O (n) внутри другой операции O (n), такой как ListA.Where(a => ListB.Contains(a)).ToList() . Каждый элемент в ListB оценивается для равенства по отношению к каждому элементу в ListA.

Как я уже сказал, мое понимание сложности ограничено, поэтому поправьте меня на это, если я ошибаюсь.

 public static bool IsSameAs(this IEnumerable source, IEnumerable target, Expression> keySelectorExpression) { // check the object if (source == null && target == null) return true; if (source == null || target == null) return false; var sourceList = source.ToList(); var targetList = target.ToList(); // check the list count :: { 1,1,1 } != { 1,1,1,1 } if (sourceList.Count != targetList.Count) return false; var keySelector = keySelectorExpression.Compile(); var groupedSourceList = sourceList.GroupBy(keySelector).ToList(); var groupedTargetList = targetList.GroupBy(keySelector).ToList(); // check that the number of grouptings match :: { 1,1,2,3,4 } != { 1,1,2,3,4,5 } var groupCountIsSame = groupedSourceList.Count == groupedTargetList.Count; if (!groupCountIsSame) return false; // check that the count of each group in source has the same count in target :: for values { 1,1,2,3,4 } & { 1,1,1,2,3,4 } // key:count // { 1:2, 2:1, 3:1, 4:1 } != { 1:3, 2:1, 3:1, 4:1 } var countsMissmatch = groupedSourceList.Any(sourceGroup => { var targetGroup = groupedTargetList.Single(y => y.Key.Equals(sourceGroup.Key)); return sourceGroup.Count() != targetGroup.Count(); }); return !countsMissmatch; } 
Interesting Posts
Давайте будем гением компьютера.