Comparer deux collections pour l'égalité, indépendamment de l'ordre des éléments qui s'y trouvent

Question

Je voudrais comparer deux collections (en C#), mais je ne suis pas sûr de la meilleure façon de le faire de manière efficace.

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 considérées comme égales si elles contiennent toutes deux les mêmes éléments (peu importe 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 vérifier 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; // les collections ne sont pas égales

foreach (Item item in collection1)
{
    if (!collection2.Contains(item))
        return false; // les collections ne sont pas égales
}

foreach (Item item in collection2)
{
    if (!collection1.Contains(item))
        return false; // les collections ne sont pas égales
}

return true; // les collections sont égales

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

Un exemple auquel je pense qui serait incorrect est:

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

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

---

Les exemples sont dans une sorte de C# (appelons cela 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 pour simplifier, mais je veux pouvoir utiliser des objets de type référence aussi (ils ne se comportent pas correctement comme clés car seule la référence de l'objet est comparée, pas le contenu).

Answer 1

erickson a presque raison : puisque vous voulez correspondre sur les comptes des doublons, vous voulez un Bag. En Java, cela ressemble à quelque chose comme ceci :

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

Je suis sûr que C# a une implémentation Set intégrée. Je l'utiliserais en premier; si la performance pose problème, vous pourriez toujours utiliser une autre implémentation Set, mais utilisez la même interface Set.

Answer 2

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'éléments. Ensuite, triez l'une des collections. Ensuite, recherchez chaque élément de la deuxième collection dans la collection triée. Si vous ne trouvez pas un élément donné, arrêtez et retournez faux. La complexité de ceci : - trier la première collection : N_Log(N) - rechercher chaque élément de la deuxième dans la première : N_LOG(N) donc vous terminez avec 2*N*LOG(N) en supposant qu'ils correspondent et que vous regardez tout. C'est similaire à la complexité de trier les deux. Cela vous permet également de vous arrêter plus tôt s'il y a une différence. Cependant, gardez à l'esprit que si les deux sont triés avant que vous ne commenciez 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, qui est idéale pour de petites collections où vous connaissez la plage des éléments, est d'utiliser un index de masque de bits. Cela vous donnera une performance O(n). Une autre alternative est d'utiliser un hachage et de le rechercher. Pour de petites collections, il est généralement préférable de faire le tri ou l'index de masque de bits. Les tables de hachage ont l'inconvénient d'une pire localité, gardez cela à l'esprit. Encore une fois, c'est seulement si vous ne vous souciez pas des doublons. Si vous voulez prendre en compte les doublons, optez pour le tri des deux.

Answer 3

Dans de nombreux cas, la seule réponse appropriée est celle d'Igor Ostrovsky, les autres réponses étant basées sur le code de hachage des objets. Mais lorsque vous générez un code de hachage pour un objet, vous le faites uniquement en fonction de ses champs IMMUTABLE - tels que le champ Id de l'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 même si les champs des différents éléments sont non égaux. Pour comparer profondément des collections, vous devez utiliser la méthode d'Igor et implémenter IEquality.

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

James

Answer 4

Autoriser les doublons dans l'IEnumerable (si les ensembles ne sont pas souhaitables/possibles) et "ignorer l'ordre" devrait vous permettre d'utiliser un .GroupBy().

Je ne suis pas un expert en matière de mesures de complexité, mais ma compréhension rudimentaire est que cela devrait être en O(n). Je comprends O(n^2) comme étant le résultat de l'exécution d'une opération en O(n) à l'intérieur d'une autre opération en 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, donc corrigez-moi si je me trompe.

public static bool IsSameAs(this IEnumerable source, IEnumerable target, Expression> keySelectorExpression)
    {
        // vérifiez l'objet
        if (source == null && target == null) return true;
        if (source == null || target == null) return false;

        var sourceList = source.ToList();
        var targetList = target.ToList();

        // vérifiez le nombre d'éléments dans la liste :: { 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();

        // vérifiez que le nombre de regroupements correspond :: { 1,1,2,3,4 } != { 1,1,2,3,4,5 }
        var groupCountIsSame = groupedSourceList.Count == groupedTargetList.Count;
        if (!groupCountIsSame) return false;

        // vérifiez que le nombre de chaque groupe dans source correspond au nombre dans target :: pour les valeurs { 1,1,2,3,4 } & { 1,1,1,2,3,4 }
        // clé:valeur
        // { 1:2, 2:1, 3:1, 4:1 } != { 1:3, 2:1, 3:1, 4:1 }
        var countsMissmatch = groupedSourceList.Any(sourceGroup =>
                                                        {
                                                            var groupCible = groupedTargetList.Single(y => y.Key.Equals(sourceGroup.Key));
                                                            return sourceGroup.Count() != groupCible.Count();
                                                        });
        return !countsMissmatch;
    }

Answer 5

Si vous comparez dans le but des Assertions de Tests Unitaires, il peut être judicieux d'ignorer un peu l'efficacité 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 par défaut affichera les différences dans le message d'erreur.

Utilisation:

using Microsoft.VisualStudio.TestTools.UnitTesting;

// définir collection1, collection2, ...

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

Méthode d'Extension d'Aide:

public static string ToCsv(
    this IEnumerable values,
    Func 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)));
}