Comparar dos colecciones para la igualdad independientemente del orden de los elementos en ellas

Me gustaría comparar dos colecciones (en C #), pero no estoy seguro de la mejor manera de implementar esto de manera eficiente.

He leído el otro hilo sobre Enumerable.SequenceEqual , pero no es exactamente lo que estoy buscando.

En mi caso, dos colecciones serían iguales si ambas contienen los mismos artículos (sin importar el orden).

Ejemplo:

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

Lo que suelo hacer es recorrer cada elemento de una colección y ver si existe en la otra colección, luego recorrer cada elemento de la otra colección y ver si existe en la primera colección. (Comienzo comparando las longitudes).

 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 

Sin embargo, esto no es del todo correcto, y probablemente no sea la manera más eficiente de comparar dos colecciones por igualdad.

Un ejemplo en el que puedo pensar que estaría mal es:

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

Lo cual sería igual a mi implementación. ¿Debo simplemente contar la cantidad de veces que se encuentra cada elemento y asegurarme de que los recuentos son iguales en ambas colecciones?


Los ejemplos están en algún tipo de C # (llamémoslo pseudo-C #), pero da tu respuesta en el idioma que desees, no importa.

Nota: Utilicé números enteros en los ejemplos para simplificar, pero también quiero poder utilizar objetos de tipo referencia (no se comportan correctamente como claves porque solo se compara la referencia del objeto, no el contenido).

Resulta que Microsoft ya tiene esto cubierto en su marco de prueba: CollectionAssert.AreEquivalent

Observaciones

Dos colecciones son equivalentes si tienen los mismos elementos en la misma cantidad, pero en cualquier orden. Los elementos son iguales si sus valores son iguales, no si se refieren al mismo objeto.

Utilizando el reflector, modifiqué el código detrás de AreEquivalent () para crear un comparador de igualdad correspondiente. Es más completo que las respuestas existentes, ya que tiene en cuenta los valores nulos, implementa IEqualityComparer y tiene cierta eficiencia y controles de casos extremos. Además, es 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; } } 

Uso de muestra:

 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 

O si solo quieres comparar dos colecciones directamente:

 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 

Finalmente, puede usar su comparador de igualdad de su elección:

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

Una solución simple y bastante eficiente es ordenar ambas colecciones y luego compararlas para la igualdad:

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

Este algoritmo es O (N * logN), mientras que su solución anterior es O (N ^ 2).

Si las colecciones tienen ciertas propiedades, es posible que pueda implementar una solución más rápida. Por ejemplo, si ambas colecciones son conjuntos de hash, no pueden contener duplicados. Además, verificar si un conjunto hash contiene algún elemento es muy rápido. En ese caso, un algoritmo similar al tuyo probablemente sea el más rápido.

Cree un diccionario “dict” y luego para cada miembro en la primera colección, dict [member] ++;

Luego, recorra la segunda colección de la misma manera, pero para cada miembro dict [miembro] -.

Al final, recorra todos los miembros del diccionario:

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

Editar: Por lo que puedo decir, esto está en el mismo orden que el algoritmo más eficiente. Este algoritmo es O (N), suponiendo que el Diccionario usa O (1) búsquedas.

Esta es mi implementación genérica (fuertemente influenciada por D.Jennings) del método de comparación (en 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; } } 

Podrías usar un Hashset . Mira el método SetEquals .

EDITAR: Me di cuenta tan pronto como planteé que esto realmente solo funciona para conjuntos: no tratará adecuadamente las colecciones que tienen elementos duplicados. Por ejemplo, {1, 1, 2} y {2, 2, 1} se considerarán iguales desde la perspectiva de este algoritmo. Si sus colecciones son conjuntos (o su igualdad se puede medir de esa manera), sin embargo, espero que encuentre útil lo siguiente.

La solución que uso es:

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

Linq hace el diccionario debajo de las sábanas, así que esto también es O (N). (Tenga en cuenta que es O (1) si las colecciones no son del mismo tamaño).

Hice un control de cordura usando el método “SetEqual” sugerido por Daniel, el método OrderBy / SequenceEquals sugerido por Igor, y mi sugerencia. Los resultados están debajo, mostrando O (N * LogN) para Igor y O (N) para el mío y el de Daniel.

Creo que la simplicidad del código de intersección de Linq lo convierte en la solución preferible.

 __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 

En el caso de que no haya repeticiones ni pedidos, se puede usar el siguiente EqualityComparer para permitir las colecciones como claves del diccionario:

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

Aquí está la implementación de ToHashSet () que utilicé. El algoritmo de código hash proviene de Effective Java (por medio de Jon Skeet).

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

La solución requiere .NET 3.5 y el espacio de nombres System.Collections.Generic . Según Microsoft , SymmetricExceptWith es una operación O (n + m) , donde n representa la cantidad de elementos en el primer conjunto ym representa el número de elementos en el segundo. Siempre puede agregar un comparador de igualdad a esta función si es necesario.

Por qué no usar. Excepto ()

 // 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

Una especie de publicación duplicada, pero mira mi solución para comparar colecciones . Es bastante simple:

Esto realizará una comparación de igualdad independientemente del orden:

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

Esto verificará si los elementos se agregaron / eliminaron:

 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 

Esto verá qué elementos del diccionario cambiaron:

 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 

Publicación original aquí .

Si usa Shouldly , puede usar ShouldAllBe with Contains.

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

Y finalmente, puedes escribir una extensión.

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

ACTUALIZAR

Existe un parámetro opcional en el método ShouldBe .

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

Erickson está casi en lo cierto: ya que quieres unir los conteos de duplicados, quieres una bolsa . En Java, esto se parece a algo así:

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

Estoy seguro de que C # tiene una implementación de Set incorporada. Yo usaría eso primero; si el rendimiento es un problema, siempre puede usar una implementación de Conjunto diferente, pero use la misma interfaz de Conjunto.

Aquí está mi variante del método de extensión de la respuesta de ohadsc, en caso de que sea útil para alguien

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

Aquí hay una solución que es una mejora con respecto a esta .

 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]); } 

Hay muchas soluciones a este problema. Si no te importan los duplicados, no tienes que ordenar los dos. Primero asegúrate de que tengan la misma cantidad de artículos. Después de eso ordenar una de las colecciones. Luego binsearch cada elemento de la segunda colección en la colección ordenada. Si no encuentra un elemento determinado, deténgase y devuelva falso. La complejidad de esto: – ordenar la primera colección: N Log (N) – buscar cada ítem desde el segundo al primero: N LOG (N) para que termine con 2 * N * LOG (N) suponiendo que coincidan y usted busca todo Esto es similar a la complejidad de ordenar ambos. También esto te da el beneficio de parar antes si hay una diferencia. Sin embargo, tenga en cuenta que si ambos se ordenan antes de entrar en esta comparación y se intenta ordenar por el uso de algo así como un qsort, la clasificación será más costosa. Hay optimizaciones para esto. Otra alternativa, que es ideal para pequeñas colecciones donde se conoce el rango de los elementos, es utilizar un índice de máscara de bits. Esto le dará un rendimiento de O (n). Otra alternativa es usar un hash y buscarlo. Para colecciones pequeñas, generalmente es mucho mejor hacer la ordenación o el índice de máscara de bits. Hashtable tiene la desventaja de una localidad peor, así que tenlo en cuenta. De nuevo, eso es solo si no te importan los duplicados. Si desea contabilizar duplicados, vaya con ordenar ambos.

En muchos casos, la única respuesta adecuada es la de Igor Ostrovsky, otras respuestas se basan en el código hash de objetos. Pero cuando genera un código hash para un objeto, lo hace solo en función de sus campos IMMUTALES, como el campo ID de objeto (en el caso de una entidad de base de datos). ¿Por qué es importante anular GetHashCode cuando el método Equals se anula?

Esto significa que si compara dos colecciones, el resultado podría ser cierto para el método de comparación, aunque los campos de los diferentes elementos no sean iguales. Para comparar profundamente las colecciones, debes usar el método de Igor e implementar IEqualirity.

Por favor, lea los comentarios míos y mr.Schnider en su publicación más votada.

James

Permitir duplicados en IEnumerable (si los conjuntos no son deseables \ posible) e “ignorar el orden” debería poder usar un .GroupBy() .

No soy un experto en las mediciones de complejidad, pero mi comprensión rudimentaria es que debería ser O (n). Entiendo O (n ^ 2) como procedente de realizar una operación O (n) dentro de otra operación O (n) como ListA.Where(a => ListB.Contains(a)).ToList() . Cada elemento en ListB se evalúa para la igualdad contra cada elemento en ListA.

Como dije, mi entendimiento sobre la complejidad es limitado, así que corrígeme si estoy equivocado.

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