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

static bool SetsContainSameElements(IEnumerable set1, IEnumerable set2) {
    var setXOR = new HashSet(set1);
    setXOR.SymmetricExceptWith(set2);
    return (setXOR.Count == 0);
}

La solution nécessite .NET 3.5 et l'espace de noms System.Collections.Generic. Selon Microsoft, SymmetricExceptWith est 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 deuxième. Vous pouvez toujours ajouter un comparateur d'égalité à cette fonction si nécessaire.

Answer 2

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(this IEnumerable list, IEnumerable equivalent)
    {
        list.ShouldAllBe(l => equivalent.Contains(l));
    }
}

MISE À JOUR

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

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

Answer 3

EDIT : J'ai réalisé dès que j'ai posté que cela fonctionne vraiment seulement 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 égaux du point de vue de cet algorithme. Si vos collections sont des ensembles (ou leur égalité peut être mesurée de cette façon), cependant, j'espère que vous trouverez l'info ci-dessous utile.

La solution que j'utilise est :

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

Linq gère le dictionnaire en coulisses, donc c'est aussi O(N). (Notez, 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 Linq en fait la solution préférée.

__Latence du Test(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

Answer 4

Dans le cas de pas de répétitions et pas d'ordre, le EqualityComparer suivant peut être utilisé pour permettre aux collections d'être des clés de dictionnaire :

public class SetComparer : IEqualityComparer> 
where T:IComparable
{
    public bool Equals(IEnumerable first, IEnumerable second)
    {
        if (first == second)
            return true;
        if ((first == null) || (second == null))
            return false;
        return first.ToHashSet().SetEquals(second);
    }

    public int GetHashCode(IEnumerable enumerable)
    {
        int hash = 17;

        foreach (T val in enumerable.OrderBy(x => x))
            hash = hash * 23 + val.GetHashCode();

        return hash;
    }
}

Ici est l'implémentation de ToHashSet() que j'ai utilisée. L'algorithme de hachage provient d'Effective Java (par l'intermédiaire de Jon Skeet).

Answer 5

Pourquoi ne pas utiliser .Except()

// Créez les sources de données IEnumerable.
string[] names1 = System.IO.File.ReadAllLines(@"../../../names1.txt");
string[] names2 = System.IO.File.ReadAllLines(@"../../../names2.txt");
// Créez la requête. Notez que la syntaxe de méthode doit être utilisée ici.
IEnumerable differenceQuery =   names1.Except(names2);
// Exécutez la requête.
Console.WriteLine("Les lignes suivantes se trouvent dans names1.txt mais pas dans names2.txt");
foreach (string s in differenceQuery)
     Console.WriteLine(s);

http://msdn.microsoft.com/en-us/library/bb397894.aspx