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

Il s'avère que Microsoft a déjà pris en charge cela dans son framework de test : CollectionAssert.AreEquivalent

Remarques

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

En utilisant Reflector, 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 a quelques vérifications d'efficacité et de cas limites. en plus, c'est Microsoft :)

public class MultiSetComparer : IEqualityComparer>
{
    private readonly IEqualityComparer m_comparer;
    public MultiSetComparer(IEqualityComparer comparer = null)
    {
        m_comparer = comparer ?? EqualityComparer.Default;
    }

    public bool Equals(IEnumerable first, IEnumerable second)
    {
        if (first == null)
            return second == null;

        if (second == null)
            return false;

        if (ReferenceEquals(first, second))
            return true;

        if (first is ICollection firstCollection && second is ICollection secondCollection)
        {
            if (firstCollection.Count != secondCollection.Count)
                return false;

            if (firstCollection.Count == 0)
                return true;
        }

        return !HaveMismatchedElement(first, second);
    }

    private bool HaveMismatchedElement(IEnumerable first, IEnumerable 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 GetElementCounts(IEnumerable enumerable, out int nullCount)
    {
        var dictionary = new Dictionary(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 enumerable)
    {
        if (enumerable == null) throw new 
            ArgumentNullException(nameof(enumerable));

        int hash = 17;

        foreach (T val in enumerable)
            hash ^= (val == null ? 42 : m_comparer.GetHashCode(val));

        return hash;
    }
}

Exemple d'utilisation :

var set = new HashSet>(new[] {new[]{1,2,3}}, new MultiSetComparer());
Console.WriteLine(set.Contains(new [] {3,2,1})); //true
Console.WriteLine(set.Contains(new [] {1, 2, 3, 3})); //false

Ou si vous voulez simplement comparer directement deux collections :

var comp = new MultiSetComparer();
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 un comparateur d'égalité de votre choix :

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

Answer 2

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

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

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

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

Answer 3

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

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

À la fin, parcourez tous les membres du dictionnaire :

    private bool SetEqual (List left, List right) {

        if (left.Count != right.Count)
            return false;

        Dictionary dict = new Dictionary();

        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 kvp in dict) {
            if (kvp.Value != 0)
                return false;
        }

        return true;

    }

Éditer : Autant que je sache, cela est de l'ordre de l'algorithme le plus efficace. Cet algorithme est de O(N), en supposant que le Dictionary utilise des recherches de O(1).

Answer 4

Ceci est ma mise en œuvre générique (fortement influencée par D.Jennings) de la méthode de comparaison (en C#):

/// 
/// Représente un service utilisé pour comparer deux collections pour égalité.
/// 
/// Le type des éléments dans les collections.
public class CollectionComparer
{
    /// 
    /// Compare le contenu de deux collections pour égalité.
    /// 
    /// La première collection.
    /// La deuxième collection.
    /// Vrai si les deux collections ont le même contenu, faux sinon.
    public bool Execute(ICollection foo, ICollection bar)
    {
        // Déclarer un dictionnaire pour compter le nombre d'occurrences des éléments dans la collection
        Dictionary itemCounts = new Dictionary();

        // Incrémenter le comptage pour chaque occurrence de l'élément dans la première collection
        foreach (T item in foo)
        {
            if (itemCounts.ContainsKey(item))
            {
                itemCounts[item]++;
            }
            else
            {
                itemCounts[item] = 1;
            }
        }

        // Mettre les clés dans une liste consultable
        List keys = new List(itemCounts.Keys);

        // Décrémenter le comptage pour chaque occurrence de l'élément dans la deuxième collection
        foreach (T item in bar)
        {
            // Essayer de trouver une clé pour l'élément
            // Les clés d'un dictionnaire sont comparées par référence, donc nous devons
            // trouver la clé d'origine qui est équivalente à l'élément
            // Vous pouvez vouloir remplacer ".Equals" pour définir ce que cela signifie pour
            // deux objets "T" d'être égaux
            T key = keys.Find(
                delegate(T listKey)
                {
                    return listKey.Equals(item);
                });

            // Vérifier si une clé a été trouvée
            if(key != null)
            {
                itemCounts[key]--;
            }
            else
            {
                // Il n'y avait aucune occurrence de cet élément dans la première collection, donc les collections ne sont pas égales
                return false;
            }
        }

        // Le comptage de chaque élément devrait être de 0 si les contenus des collections sont égaux
        foreach (int value in itemCounts.Values)
        {
            if (value != 0)
            {
                return false;
            }
        }

        // Les collections sont égales
        return true;
    }
}

Answer 5

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