Comparar dos colecciones para la igualdad independientemente del orden de los elementos en ellos
https://stackoverflow.com/questions/50098
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
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 el Enumerable.SequenceEqual, pero no es exactamente lo que estoy buscando.
En mi caso, dos colecciones serían iguales si contienen los mismos elementos (no importa el orden).
Ejemplo:
collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};
collection1 == collection2; // true
Lo que suele hacer es recorrer cada elemento de una colección y ver si existe en la otra colección, luego pase a través de cada elemento de la colección y ver si existe en el primero de la colección.(Empiezo por la comparación de 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 totalmente correcto, y probablemente no sea la forma más eficiente de hacer comparar dos colecciones para la igualdad.
Un ejemplo que se me ocurre que sería un error es:
collection1 = {1, 2, 3, 3, 4}
collection2 = {1, 2, 2, 3, 4}
Que sería igual con mi aplicación.Debo contar el número de veces que cada elemento se encuentra y asegúrese de que las cuentas son iguales en ambas colecciones?
Los ejemplos se encuentran en algún tipo de C# (vamos a llamar pseudo-C#), pero dar su respuesta en el idioma que usted desea, no importa.
Nota: He utilizado enteros en los ejemplos de la simplicidad, pero quiero ser capaz de utilizar de referencia-tipo de objetos (que no se comportan correctamente como claves porque sólo la referencia del objeto es, en comparación, no el contenido).
Solución
Resulta que Microsoft ya esta cubierto en su marco de pruebas: CollectionAssert.AreEquivalent
Comentarios
Dos colecciones son equivalentes si se tienen los mismos elementos en la misma la cantidad, pero en cualquier orden.Elementos son iguales si sus valores son iguales, no se si se refieren al mismo objeto.
Mediante reflector, he modificado el código detrás de AreEquivalent() para crear una correspondiente comparador de igualdad.Es más completa que las respuestas existentes, ya que toma valores nulos en cuenta, implementa IEqualityComparer y tiene algunas eficiencia y el caso extremo de cheques.además, es Microsoft :)
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;
}
}
Ejemplo de uso:
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
O si usted simplemente desea comparar dos colecciones directamente:
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
Por último, puede utilizar un comparador de igualdad de su elección:
var strcomp = new MultiSetComparer<string>(StringComparer.OrdinalIgnoreCase);
Console.WriteLine(strcomp.Equals(new[] {"a", "b"}, new []{"B", "A"})); //true
Otros consejos
Un simple y bastante eficiente solución es ordenar ambas colecciones y luego compararlas con las de la igualdad:
bool equal = collection1.OrderBy(i => i).SequenceEqual(
collection2.OrderBy(i => i));
Este algoritmo es O(N*logN), mientras que la solución anterior es O(N^2).
Si las colecciones tienen ciertas propiedades, usted puede ser capaz de implementar una solución más rápida.Por ejemplo, si sus dos colecciones de hash de conjuntos, que no puede contener duplicados.También, la comprobación de si un hash que contiene alguno de los elementos es muy rápido.En ese caso, un algoritmo similar a la tuya probablemente sería más rápido.
Crear un Diccionario "dict" y, a continuación, para cada uno de los miembros en la primera colección, hacer dict[miembro]++;
A continuación, un bucle en la segunda colección de la misma manera, pero para cada miembro de dict[miembro]--.
Al final, bucle a través de todos los miembros en el diccionario:
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;
}
Editar:Como puedo saber que esto es en el mismo orden como el más eficiente del algoritmo.Este algoritmo es O(N), suponiendo que el Diccionario de usos O(1) búsquedas.
Este es mi (fuertemente influenciado por D. Jennings) genérico aplicación del método de comparación (en 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;
}
}
EDITAR:Me di cuenta de que tan pronto como me plantea que esto realmente sólo funciona para los juegos -- no tratar adecuadamente con las colecciones que tiene elementos duplicados.Por ejemplo, { 1, 1, 2 } y { 2, 2, 1 } se consideran iguales a partir de este algoritmo perspectiva.Si tus colecciones son conjuntos (o, en su igualdad se puede medir de esa manera), sin embargo, espero que usted encuentre los de abajo útil.
La solución que yo uso es:
return c1.Count == c2.Count && c1.Intersect(c2).Count() == c1.Count;
Linq hace el diccionario de la cosa de debajo de las mantas, este también es O(N).(Nota, es O(1) si las colecciones no tienen el mismo tamaño).
Hice una comprobación de validez, utilizando la "SetEqual" método propuesto por Daniel, el OrderBy/SequenceEquals método propuesto por Igor, y mi sugerencia.Los resultados están por debajo, mostrando O(N*LogN) de Igor y O(N) para el mío y el de Daniel.
Creo que la simplicidad de la Linq se cruzan código hace que sea la mejor solución.
__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 se repite y no hay orden, las siguientes EqualityComparer se puede utilizar para permitir colecciones como claves del diccionario:
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;
}
}
Aquí es el ToHashSet() aplicación que he usado.El código hash algoritmo viene de Efectivo de Java (por la forma de Jon Skeet).
static bool SetsContainSameElements<T>(IEnumerable<T> set1, IEnumerable<T> set2) {
var setXOR = new HashSet<T>(set1);
setXOR.SymmetricExceptWith(set2);
return (setXOR.Count == 0);
}
Solución requiere .NET 3.5 y la System.Collections.Generic espacio de nombres. Según Microsoft, SymmetricExceptWith es un O(n + m) la operación, con n representa el número de elementos del primer conjunto y m representa el número de elementos en la segunda.Siempre se puede añadir un comparador de igualdad para 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<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);
Si usted utiliza Shouldly, usted puede utilizar ShouldAllBe con los Contiene.
collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};
collection1.ShouldAllBe(item=>collection2.Contains(item)); // true
Y por último, usted puede escribir una extensión.
public static class ShouldlyIEnumerableExtensions
{
public static void ShouldEquivalentTo<T>(this IEnumerable<T> list, IEnumerable<T> equivalent)
{
list.ShouldAllBe(l => equivalent.Contains(l));
}
}
ACTUALIZACIÓN
Un parámetro opcional que existe en ShouldBe método.
collection1.ShouldBe(collection2, ignoreOrder: true); // true
Un duplicado post de las clases, pero echa un vistazo a mi solución para comparar colecciones.Es bastante simple:
Se realizará una comparación de igualdad, independientemente de orden:
var list1 = new[] { "Bill", "Bob", "Sally" };
var list2 = new[] { "Bob", "Bill", "Sally" };
bool isequal = list1.Compare(list2).IsSame;
Esto comprobará si los artículos se han añadido / quitado:
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
Este se vea lo que los elementos en el diccionario cambiado:
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
Post Original aquí.
erickson es casi la derecha:puesto que usted desea hacer coincidir en la cuenta de duplicados, usted quiere un Bolsa.En Java, esto parece algo como:
(new HashBag(collection1)).equals(new HashBag(collection2))
Estoy seguro de que C# dispone de un Conjunto integrado de aplicación.Yo la uso primero;si el rendimiento es un problema, siempre se puede usar un Conjunto diferente de implementación, pero utilizan el mismo Conjunto de interfaz.
Este es mi método de extensión de la variante de ohadsc la respuesta, en caso de que sea útil a alguien
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;
}
}
Aquí hay una solución que es una mejora con respecto a este.
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]);
}
Hay muchas soluciones a este problema.Si usted no se preocupan por duplicados, usted no tiene que ordenar tanto.Primero, asegúrate de que tengan el mismo número de elementos.Después de ese tipo en una de las colecciones.Luego binsearch cada elemento de la segunda colección en la colección ordenada.Si usted no encuentra un elemento dado parar y devolver false.La complejidad de este:- clasificación de la primera colección:NLog(N) - buscando en cada elemento de la segunda a la primera:NLOG(N) así que al final termina con 2*N*LOG(N), suponiendo que coinciden y se mira de todo.Esto es similar a la complejidad de la clasificación de ambos.También esto le da la ventaja a la parada antes si hay una diferencia.Sin embargo, tenga en cuenta que si ambos se ordenan antes de entrar en esta comparación e intenta ordenar por usar algo como un qsort, la clasificación será más caro.Hay optimizaciones para este.Otra alternativa, que es ideal para pequeñas colecciones, donde se conoce el rango de los elementos es el uso de una máscara de bits de índice.Esto le dará un O(n) el rendimiento.Otra alternativa es utilizar un hash y mira hacia arriba.Para las pequeñas colecciones de las que normalmente es mucho mejor hacerlo de la ordenación o la máscara de bits de índice.Hashtable tienen la desventaja de peor localidad así que tenlo en cuenta.De nuevo, eso es sólo si usted no se preocupan por los duplicados.Si usted desea tener en cuenta para duplicados ir con la clasificación de ambos.
En muchos casos, la única respuesta adecuada es la de Igor Ostrovsky , otras respuestas se basan en objetos de código hash.Pero cuando se genera un código hash de un objeto de hacerlo únicamente con base en su INMUTABLE campos - como el campo Id de objeto (en el caso de una entidad de base de datos) - ¿Por qué es importante reemplazar GetHashCode cuando es Igual método se reemplaza?
Esto significa , que si usted comparar dos colecciones , el resultado podría ser cierto en el método de comparación aunque los campos de los diferentes elementos no son iguales .A la profunda comparar colecciones , es necesario utilizar Igor método y aplicar IEqualirity .
Por favor, lea los comentarios de me and mr.Schnider en su mayoría votaron post.
James
Permite duplicados en el IEnumerable<T> (si los conjuntos son no deseables\posibles) y "haciendo caso omiso de la orden de" usted debería ser capaz de utilizar un .GroupBy().
Yo no soy un experto en la complejidad de las mediciones, pero mi entendimiento rudimentario es que esto debería ser O(n).Entiendo que O(n^2) como la que proviene de la realización de una operación O(n) dentro de otra operación O(n) como ListA.Where(a => ListB.Contains(a)).ToList().Cada elemento en ListB es evaluado por la igualdad en contra de cada elemento en la ListA.
Como dije, mi comprensión de la complejidad es limitado, así que me corrija si estoy equivocado.
public static bool IsSameAs<T, TKey>(this IEnumerable<T> source, IEnumerable<T> target, Expression<Func<T, TKey>> 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;
}
Esta sencilla solución las fuerzas de la IEnumerable's de tipo genérico para implementar IComparable.Porque de
OrderBy's definición.
Si usted no quiere hacer tal suposición, pero aún desea utilizar esta solución, puede utilizar el siguiente fragmento de código :
bool equal = collection1.OrderBy(i => i?.GetHashCode())
.SequenceEqual(collection2.OrderBy(i => i?.GetHashCode()));
