Comparer deux collections pour l'égalité quel que soit l'ordre des éléments qu'elles contiennent

Je voudrais comparer deux collections (en C #), mais je ne suis pas sûr de la meilleure façon de l'implémenter efficacement.

J'ai lu l'autre fil de discussion sur Enumerable.SequenceEqual , mais ce n'est pas exactement ce que je recherche.

Dans mon cas, deux collections seraient égales si elles contiennent toutes les deux les mêmes éléments (quel que soit l'ordre).

Exemple:

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

collection1 == collection2; // true

Ce que je fais habituellement, c'est de parcourir chaque élément d'une collection et de voir s'il existe dans l'autre collection, puis de parcourir chaque élément de l'autre collection et de voir s'il existe dans la première collection. (Je commence par comparer les longueurs).

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

Cependant, ce n'est pas tout à fait correct et ce n'est probablement pas le moyen le plus efficace de comparer deux collections pour l'égalité.

Un exemple auquel je pense que ce serait faux est:

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

Ce qui serait égal à ma mise en œuvre. Dois-je simplement compter le nombre de fois où chaque élément est trouvé et m'assurer que les nombres sont égaux dans les deux collections?

Les exemples sont dans une sorte de C # (appelons-le pseudo-C #), mais donnez votre réponse dans la langue que vous souhaitez, cela n'a pas d'importance.

Remarque: j'ai utilisé des entiers dans les exemples par souci de simplicité, mais je veux pouvoir utiliser également des objets de type référence (ils ne se comportent pas correctement comme des clés car seule la référence de l'objet est comparée, pas le contenu).

Il s'avère que Microsoft a déjà couvert cela dans son cadre de test: CollectionAssert.AreEquivalent

Remarques

Deux collections sont équivalentes si elles ont les mêmes éléments dans la même quantité, mais dans n'importe quel ordre. Les éléments sont égaux si leurs valeurs sont égales, pas s'ils font référence au même objet.

À l'aide du réflecteur, j'ai modifié le code derrière AreEquivalent () pour créer un comparateur d'égalité correspondant. Il est plus complet que les réponses existantes, car il prend en compte les valeurs nulles, implémente IEqualityComparer et offre des vérifications d'efficacité et de cas de pointe. en plus, c'est 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;
    }
}

Exemple d'utilisation:

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

Ou si vous souhaitez simplement comparer directement deux collections:

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

Enfin, vous pouvez utiliser votre comparateur d'égalité de votre choix:

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

Une solution simple et assez efficace consiste à trier les deux collections puis à les comparer pour l'égalité:

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

Cet algorithme est O (N * logN), tandis que votre solution ci-dessus est O (N ^ 2).

Si les collections ont certaines propriétés, vous pourrez peut-être implémenter une solution plus rapide. Par exemple, si vos deux collections sont des ensembles de hachage, elles ne peuvent pas contenir de doublons. De plus, vérifier si un ensemble de hachage contient un élément est très rapide. Dans ce cas, un algorithme similaire au vôtre serait probablement le plus rapide.

Créez un dictionnaire "dict", puis pour chaque membre de la première collection, faites dict [membre] ++;

Ensuite, parcourez la deuxième collection de la même manière, mais pour chaque membre, faites dict [membre] -.

À la fin, parcourez tous les membres du dictionnaire:

    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;

    }

Edit: Autant que je sache, c'est dans le même ordre que l'algorithme le plus efficace. Cet algorithme est O (N), en supposant que le dictionnaire utilise les recherches O (1).

Voici mon implémentation générique (fortement influencée par D.Jennings) de la méthode de comparaison (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;
    }
}

Vous pouvez utiliser un Hashset . Regardez la méthode SetEquals .

Si vous utilisez Shouldly , vous pouvez utiliser ShouldAllBe avec Contains.

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

collection1.ShouldAllBe(item=>collection2.Contains(item)); // true

Et enfin, vous pouvez écrire une extension.

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

METTRE À JOUR

Un paramètre facultatif existe sur la méthode ShouldBe .

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

EDIT: J'ai réalisé dès que j'ai posé que cela ne fonctionne vraiment que pour les ensembles - cela ne traitera pas correctement les collections qui ont des éléments en double. Par exemple, {1, 1, 2} et {2, 2, 1} seront considérés comme égaux du point de vue de cet algorithme. Si vos collections sont des ensembles (ou que leur égalité peut être mesurée de cette façon), j'espère que vous trouverez ce qui suit utile.

La solution que j'utilise est:

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

Linq fait le truc du dictionnaire sous les couvertures, donc c'est aussi O (N). (Notez que c'est O (1) si les collections ne sont pas de la même taille).

J'ai fait une vérification de bon sens en utilisant la méthode "SetEqual" suggérée par Daniel, la méthode OrderBy / SequenceEquals suggérée par Igor et ma suggestion. Les résultats sont ci-dessous, montrant O (N * LogN) pour Igor et O (N) pour le mien et celui de Daniel.

Je pense que la simplicité du code d'intersection de Linq en fait la solution préférable.

__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 cas d'absence de répétition et d'ordre, le EqualityComparer suivant peut être utilisé pour autoriser les collections en tant que clés de dictionnaire:

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

Voici l'implémentation ToHashSet () que j'ai utilisée. L' algorithme de code de hachage provient de Effective Java (via 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 solution nécessite .NET 3.5 et l' System.Collections.Genericespace de noms. Selon Microsoft , SymmetricExceptWithest une opération O (n + m) , avec n représentant le nombre d'éléments dans le premier ensemble et m représentant le nombre d'éléments dans le second. Vous pouvez toujours ajouter un comparateur d'égalité à cette fonction si nécessaire.

Pourquoi ne pas utiliser .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

Un article en double, mais consultez ma solution pour comparer les collections . C'est assez simple:

Cela effectuera une comparaison d'égalité quel que soit l'ordre:

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

Cela vérifiera si des éléments ont été ajoutés / supprimés:

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

Cela verra quels éléments du dictionnaire ont changé:

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

Message original ici .

erickson a presque raison: puisque vous voulez faire correspondre le nombre de doublons, vous voulez un sac . En Java, cela ressemble à quelque chose comme:

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

Je suis sûr que C # a une implémentation Set intégrée. J'utiliserais cela en premier; si les performances sont un problème, vous pouvez toujours utiliser une implémentation Set différente, mais utiliser la même interface Set.

Voici ma variante de méthode d'extension de la réponse d'Ohadsc, au cas où cela serait utile à quelqu'un

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

Voici une solution qui est une amélioration par rapport à celle-ci .

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

Il existe de nombreuses solutions à ce problème. Si vous ne vous souciez pas des doublons, vous n'avez pas à trier les deux. Assurez-vous d'abord qu'ils ont le même nombre d'articles. Après cela, une des collections. Recherchez ensuite chaque élément de la deuxième collection de la collection triée. Si vous ne trouvez pas un élément donné, arrêtez et renvoyez false. La complexité de ceci: - tri de la première collection: N Log (N) - recherche de chaque élément du deuxième au premier: NLOG (N) donc vous vous retrouvez avec 2 * N * LOG (N) en supposant qu'ils correspondent et vous recherchez tout. Ceci est similaire à la complexité du tri des deux. Cela vous donne également l'avantage d'arrêter plus tôt s'il y a une différence. Cependant, gardez à l'esprit que si les deux sont triés avant d'entrer dans cette comparaison et que vous essayez de trier en utilisant quelque chose comme un qsort, le tri sera plus coûteux. Il existe des optimisations pour cela. Une autre alternative, idéale pour les petites collections où vous connaissez la plage des éléments, consiste à utiliser un index de masque de bits. Cela vous donnera une performance O (n). Une autre alternative consiste à utiliser un hachage et à le rechercher. Pour les petites collections, il est généralement préférable de faire le tri ou l'index du masque de bits. Hashtable a l'inconvénient de pire localité, alors gardez cela à l'esprit. Encore une fois, ce n'est que si vous ne le faites pas t se soucier des doublons. Si vous souhaitez tenir compte des doublons, optez pour le tri des deux.

Dans de nombreux cas, la seule réponse appropriée est celle d'Igor Ostrovsky, d'autres réponses sont basées sur le code de hachage d'objets. Mais lorsque vous générez un code de hachage pour un objet, vous le faites uniquement en fonction de ses champs IMMUTABLES - tels que le champ Id d'objet (dans le cas d'une entité de base de données) - Pourquoi est-il important de remplacer GetHashCode lorsque la méthode Equals est remplacée?

Cela signifie que si vous comparez deux collections, le résultat peut être vrai pour la méthode de comparaison même si les champs des différents éléments ne sont pas égaux. Pour comparer en profondeur les collections, vous devez utiliser la méthode d'Igor et implémenter IEqualirity.

Veuillez lire les commentaires de moi et de M. Schnider sur son poste le plus voté.

James

En autorisant les doublons dans le IEnumerable<T>(si les ensembles ne sont pas souhaitables \ possible) et "ignorer l'ordre", vous devriez pouvoir utiliser un .GroupBy().

Je ne suis pas un expert des mesures de complexité, mais ma compréhension rudimentaire est que cela devrait être O (n). Je comprends O (n ^ 2) comme venant de l'exécution d'une opération O (n) dans une autre opération O (n) comme ListA.Where(a => ListB.Contains(a)).ToList(). Chaque élément de ListB est évalué pour l'égalité par rapport à chaque élément de ListA.

Comme je l'ai dit, ma compréhension de la complexité est limitée, alors corrigez-moi si je me trompe.

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

Cette solution simple force l' IEnumerableimplémentation du type générique de IComparable. En raison de OrderByla définition de.

Si vous ne souhaitez pas faire une telle hypothèse mais que vous souhaitez tout de même utiliser cette solution, vous pouvez utiliser le morceau de code suivant:

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

Si vous comparez dans le but d'assertions de test unitaire, il peut être judicieux de jeter une certaine efficacité par la fenêtre et de simplement convertir chaque liste en une représentation sous forme de chaîne (csv) avant de faire la comparaison. De cette façon, le message d'assertion de test par défaut affichera les différences dans le message d'erreur.

Usage:

using Microsoft.VisualStudio.TestTools.UnitTesting;

// define collection1, collection2, ...

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

Méthode d'extension d'assistance:

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