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 generalmente hago 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 forma más eficiente de comparar dos colecciones para la igualdad.

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

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

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

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

Nota: Usé números enteros en los ejemplos por simplicidad, pero también quiero poder usar 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.

Usando 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 algunas comprobaciones de eficiencia y 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 la 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 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

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

Una solución simple y bastante eficiente es clasificar ambas colecciones y luego compararlas para lograr 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, puede implementar una solución más rápida. Por ejemplo, si ambas colecciones son conjuntos 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 suyo probablemente sería el más rápido.

Cree un diccionario "dict" y luego, para cada miembro de la primera colección, haga dict [member] ++;

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

Al final, repita 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 utilice búsquedas O (1).

Esta es mi implementación genérica (muy 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;
    }
}

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

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

EDITAR: me di cuenta tan pronto como planteé que esto realmente solo funciona para conjuntos, no tratará adecuadamente con colecciones que tienen elementos duplicados. Por ejemplo, {1, 1, 2} y {2, 2, 1} se considerarán iguales desde la perspectiva de este algoritmo. Sin embargo, si sus colecciones son conjuntos (o su igualdad se puede medir de esa manera), 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 lo del diccionario debajo de las cubiertas, por lo que también es O (N). (Tenga en cuenta que es O (1) si las colecciones no son del mismo tamaño).

Hice una comprobación de cordura utilizando el método "SetEqual" sugerido por Daniel, el método OrderBy / SequenceEquals sugerido por Igor y mi sugerencia. Los resultados están a continuación, 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 se repitan ni se ordene, se puede usar el siguiente EqualityComparer para permitir colecciones como claves de 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í está la implementación ToHashSet () que utilicé. El algoritmo de código hash proviene de Effective Java (a través 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);
}

La solución requiere .NET 3.5 y el System.Collections.Genericespacio de nombres. Según Microsoft , SymmetricExceptWithes una operación O (n + m) , donde n representa el número 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 .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

Una 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 se agregaron / eliminaron elementos:

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 aquí .

erickson tiene casi razón: dado que desea hacer coincidir los recuentos de duplicados, quiere una bolsa . En Java, esto se parece a:

(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 Set diferente, pero use la misma interfaz de Set.

Aquí está mi variante de 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]);
    }

Hay muchas soluciones a este problema. Si no te importan los duplicados, no tienes que ordenar ambos. Primero asegúrese de que tengan la misma cantidad de artículos. Después de eso, una de las colecciones. Luego, busque cada elemento de la segunda colección en la colección ordenada. Si no encuentra un artículo determinado, deténgase y devuelva falso. La complejidad de esto: - ordenar la primera colección: N Log (N) - buscar cada elemento del segundo al primero: NLOG (N) para que termines con 2 * N * LOG (N) suponiendo que coincidan y busques todo. Esto es similar a la complejidad de ordenar ambos. Además, esto le brinda el beneficio de detenerse antes si hay una diferencia. Sin embargo, tenga en cuenta que si ambos se ordenan antes de pasar a esta comparación e intenta ordenarlos usando algo como qsort, la clasificación será más costosa. Hay optimizaciones para esto. Otra alternativa, que es ideal para pequeñas colecciones en las que conoce el rango de los elementos, es usar un índice de máscara de bits. Esto le dará un rendimiento O (n). Otra alternativa es usar un hash y buscarlo. Para colecciones pequeñas, generalmente es mucho mejor hacer la clasificación o el índice de máscara de bits. Hashtable tiene la desventaja de una peor localidad, así que tenlo en cuenta. De nuevo, eso solo si no lo haces No importa los duplicados. Si desea tener en cuenta los duplicados, vaya ordenando ambos.

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

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 colecciones en profundidad, debe utilizar el método de Igor e implementar IEqualirity.

Lea los comentarios míos y del Sr.Schnider en su publicación más votada.

James

Permitiendo duplicados en IEnumerable<T>(si los conjuntos no son deseables \ posibles) e "ignorando el orden", debería poder usar a .GroupBy().

No soy un experto en las mediciones de complejidad, pero mi comprensión rudimentaria es que esto debería ser O (n). Entiendo que O (n ^ 2) proviene de realizar una operación O (n) dentro de otra operación O (n) como ListA.Where(a => ListB.Contains(a)).ToList(). Se evalúa la igualdad de cada elemento de la Lista B con respecto a cada elemento de la Lista A.

Como dije, mi comprensión de la complejidad es limitada, así que corrígeme si me equivoco.

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 solución simple obliga IEnumerablea implementar el tipo genérico IComparable. Por OrderByla definición de.

Si no desea hacer tal suposición pero aún quiere usar esta solución, puede usar el siguiente código:

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

Si se compara con el propósito de Afirmaciones de Prueba de Unidad, puede tener sentido tirar algo de eficiencia por la ventana y simplemente convertir cada lista en una representación de cadena (csv) antes de hacer la comparación. De esa manera, el mensaje de Aserción de prueba predeterminado mostrará las diferencias dentro del mensaje de error.

Uso:

using Microsoft.VisualStudio.TestTools.UnitTesting;

// define collection1, collection2, ...

Assert.Equal(collection1.OrderBy(c=>c).ToCsv(), collection2.OrderBy(c=>c).ToCsv());

Método de extensión auxiliar:

public static string ToCsv<T>(
    this IEnumerable<T> values,
    Func<T, string> selector,
    string joinSeparator = ",")
{
    if (selector == null)
    {
        if (typeof(T) == typeof(Int16) ||
            typeof(T) == typeof(Int32) ||
            typeof(T) == typeof(Int64))
        {
            selector = (v) => Convert.ToInt64(v).ToStringInvariant();
        }
        else if (typeof(T) == typeof(decimal))
        {
            selector = (v) => Convert.ToDecimal(v).ToStringInvariant();
        }
        else if (typeof(T) == typeof(float) ||
                typeof(T) == typeof(double))
        {
            selector = (v) => Convert.ToDouble(v).ToString(CultureInfo.InvariantCulture);
        }
        else
        {
            selector = (v) => v.ToString();
        }
    }

    return String.Join(joinSeparator, values.Select(v => selector(v)));
}