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

162

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).

mbillard
la source
1
Et l'algorithme? Toutes les réponses sont liées par comparer quelque chose, les listes génériques comparent linq etc. Avons-nous vraiment promis à quelqu'un que nous n'utiliserons jamais l'algorithme en tant que programmeur à l'ancienne?
Nuri YILMAZ
Vous ne vérifiez pas l'égalité que vous vérifiez pour l'équivalence. C'est pointilleux mais une distinction importante. Et il y a longtemps. C'est un bon Q + R.
CAD bloke
Vous pourriez être intéressé par cet article , qui présente une version optimisée de la méthode basée sur le dictionnaire décrite ci-dessous. Un problème avec la plupart des approches de dictionnaire simples est qu'elles ne gèrent pas correctement les valeurs nulles car la classe Dictionary de .NET n'autorise pas les clés nulles.
ChaseMedallion

Réponses:

112

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
Ohad Schneider
la source
7
Je ne suis pas sûr à 100% mais je pense que votre réponse viole les conditions d'utilisation de Microsoft contre l'ingénierie inverse.
Ian Dallas
1
Bonjour Ohad, S'il vous plaît lire le long débat suivant dans le sujet, stackoverflow.com/questions/371328/... Si vous changez le hashcode de l'objet, alors qu'il est dans un hashset il s'interrompra avec l'action appropriée du hashset et pourrait provoquer une exception. La règle est la suivante: si deux objets sont égaux, ils doivent avoir le même code de hachage. Si deux objets ont le même hashcode, il n'est pas indispensable qu'ils soient égaux. Le hachcode doit rester le même pendant toute la durée de vie de l'objet! C'est pourquoi vous encouragez ICompareable et IEqualrity.
James Roeiter
2
@JamesRoeiter Peut-être que mon commentaire était trompeur. Lorsqu'un dictionnaire rencontre un hashcode qu'il contient déjà, il vérifie l' égalité réelle avec un EqualityComparer(soit celui que vous avez fourni, soit EqualityComparer.Default, vous pouvez vérifier Reflector ou la source de référence pour le vérifier). Certes, si les objets changent (et en particulier leur hashcode change) pendant que cette méthode est en cours d'exécution, les résultats sont inattendus, mais cela signifie simplement que cette méthode n'est pas thread-safe dans ce contexte.
Ohad Schneider le
1
@JamesRoeiter Supposons que x et y sont deux objets que nous voulons comparer. S'ils ont des codes de hachage différents, nous savons qu'ils sont différents (car des éléments égaux ont des codes de hachage égaux) et l'implémentation ci-dessus est correcte. S'ils ont le même hashcode, l'implémentation du dictionnaire vérifiera l' égalité réelle en utilisant le spécifié EqualityComparer(ou EqualityComparer.Defaultsi aucun n'a été spécifié) et à nouveau l'implémentation est correcte.
Ohad Schneider du
1
@CADbloke la méthode doit être nommée à Equalscause de l' IEqualityComparer<T>interface. Ce que vous devriez regarder, c'est le nom du comparateur lui-même . Dans ce cas, c'est MultiSetComparerce qui a du sens.
Ohad Schneider
98

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.

Sani Singh Huttunen
la source
1
Il vous suffit d'ajouter un using System.Linq; premier pour le faire fonctionner
Junior Mayhé
si ce code est dans une boucle et que collection1 est mis à jour et que collection2 reste intacte, notez que même lorsque les deux collections ont le même objet, le débogueur afficherait false pour cette variable «égale».
Junior Mayhé
5
@Chaulky - Je pense que OrderBy est nécessaire. Voir: dotnetfiddle.net/jA8iwE
Brett
Quelle était l'autre réponse appelée «ci-dessus»? Peut-être stackoverflow.com/a/50465/3195477 ?
UuDdLrLrSs
32

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).

Daniel Jennings
la source
C'est presque ce que je veux. Cependant, j'aimerais pouvoir le faire même si je n'utilise pas d'entiers. Je voudrais utiliser des objets de référence, mais ils ne se comportent pas correctement comme des clés dans les dictionnaires.
mbillard
Mono, votre question est sans objet si vos articles ne sont pas comparables. Si elles ne peuvent pas être utilisées comme clés dans le dictionnaire, aucune solution n'est disponible.
skolima
1
Je pense que Mono voulait dire que les clés ne sont pas triables. Mais la solution de Daniel est clairement destinée à être implémentée avec une table de hachage, pas un arbre, et fonctionnera tant qu'il y aura un test d'équivalence et une fonction de hachage.
erickson
Bien sûr voté pour l'aide, mais pas accepté car il manque un point important (que je couvre dans ma réponse).
mbillard
1
FWIW, vous pouvez simplifier votre dernière boucle foreach et déclaration de retour avec ceci:return dict.All(kvp => kvp.Value == 0);
Tyson Williams
18

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;
    }
}
mbillard
la source
12
Bon travail, mais Note: 1. Contrairement à la solution de Daniel Jennings, ce n'est pas O (N) mais plutôt O (N ^ 2), à cause de la fonction find à l'intérieur de la boucle foreach sur la collection de barres; 2. Vous pouvez généraliser la méthode pour accepter IEnumerable <T> au lieu de ICollection <T> sans autre modification du code
Ohad Schneider
The keys of a dictionary are compared by reference, so we have to find the original key that is equivalent to the "item"- ce n'est pas vrai. L'algorithme est basé sur de fausses hypothèses et bien qu'il fonctionne, il est terriblement inefficace.
Antonín Lejsek
10

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

Joël Gauvreau
la source
2
Bien sûr, l'utilisation d'un HashSet ne suppose aucun doublon, mais si c'est le cas, HashSet est la meilleure façon de procéder
Mark Cidade
7

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
Pier-Lionel Sgard
la source
1
Je viens de trouver sur la dernière version qu'il existe un paramètre bool ignoreOrdersur la méthode ShouldBe .
Pier-Lionel Sgard
5

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

la source
Le seul problème avec ce code est qu'il ne fonctionne que lors de la comparaison des types de valeur ou de la comparaison des pointeurs aux types de référence. Je pourrais avoir deux instances différentes du même objet dans les collections, je dois donc être en mesure de spécifier comment les comparer. Pouvez-vous transmettre un délégué de comparaison à la méthode intersect?
mbillard
Bien sûr, vous pouvez transmettre un délégué de comparateur. Mais, notez la limitation ci-dessus concernant les ensembles que j'ai ajoutés, qui met une limite significative à son applicabilité.
La méthode Intersect renvoie une collection distincte. Étant donné a = {1,1,2} et b = {2,2,1}, a.Intersect (b) .Count ()! = A.Count, ce qui fait que votre expression renvoie correctement false. {1,2} .Count! = {1,1,2} .Count Voir le lien [/ link] (Notez que les deux côtés sont séparés avant la comparaison.)
Griffin
5

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).

Ohad Schneider
la source
Quel est l'intérêt de la classe Serializable for Comparer? : o Vous pouvez également changer l'entrée pour ISet<T>exprimer qu'elle est destinée aux ensembles (c'est-à-dire pas de doublons).
nawfal
@nawfal merci, je ne sais pas à quoi je pensais quand je l'ai marqué Sérialisable ... Quant à ISet, l'idée ici était de traiter le IEnumerablecomme un ensemble (parce que vous avez un IEnumerablepour commencer), tout en considérant les 0 votes positifs en plus 5 ans qui n'ont peut-être pas été l'idée la plus pointue: P
Ohad Schneider
4
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.

palswim
la source
3

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

Korayem
la source
2
Exceptne fonctionnera pas pour compter les éléments en double. Il retournera vrai pour les ensembles {1,2,2} et {1,1,2}.
Cristian Diaconescu
@CristiDiaconescu vous pouvez faire un ".Distinct ()" d'abord pour supprimer les doublons
Korayem
Le PO demande [1, 1, 2] != [1, 2, 2]. L'utilisation Distinctles rendrait égaux.
Cristian Diaconescu
2

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 .

user329244
la source
1

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.

James A. Rosen
la source
1

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;
    }
}
Eric J.
la source
Est-ce que cela fonctionne bien, des idées?
nawfal
Je ne l'utilise que pour les petites collections, donc je n'ai pas pensé à la complexité Big-O ni fait de benchmarking. HaveMismatchedElements seul est O (M * N), il peut donc ne pas fonctionner correctement pour les grandes collections.
Eric J.
Si les IEnumerable<T>s sont des requêtes, appeler Count()n'est pas une bonne idée. L'approche originale de la réponse d'Ohad consistant à vérifier si elles le sont ICollection<T>est la meilleure idée.
nawfal
1

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]);
    }
N73k
la source
0

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.


la source
0

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

James Roeiter
la source
0

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;
    }
Josh Gust
la source
0

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()));
Jo Ham
la source
0

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)));
}
crokusek
la source