.net - otra - comparar si dos arraylist son iguales
Comparar dos colecciones para la igualdad independientemente del orden de los elementos en ellas (16)
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).
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<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 esta .
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]);
}
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<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: 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.
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<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;
}
}
Here está la implementación de ToHashSet () que utilicé. El algoritmo de código hash proviene de Effective Java (por medio de Jon Skeet).
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
Esta es mi implementación genérica (fuertemente influenciada por D.Jennings) 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;
}
}
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.
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);
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<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;
}
}
Uso de muestra:
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 solo quieres 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
Finalmente, puede usar su 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
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<T>(this IEnumerable<T> list, IEnumerable<T> equivalent)
{
list.ShouldAllBe(l => equivalent.Contains(l));
}
}
ACTUALIZAR
Existe un parámetro opcional en el método ShouldBe .
collection1.ShouldBe(collection2, ignoreOrder: true); // true
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<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
Publicación original here .
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.
erickson está casi en lo cierto: ya que quieres unir los conteos de duplicados, quieres una Bag . 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.
static bool SetsContainSameElements<T>(IEnumerable<T> set1, IEnumerable<T> set2) {
var setXOR = new HashSet<T>(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.