Le moyen le plus rapide de comparer deux List<>

Question

Quelle est la méthode la plus rapide (et la moins gourmande en ressources) pour comparer deux listes massives (>50.000 articles) et obtenir ainsi deux listes comme celles ci-dessous :

1. les éléments qui apparaissent dans la première liste mais pas dans la seconde.
2. les éléments qui apparaissent dans la deuxième liste mais pas dans la première.

Actuellement, je travaille avec la liste ou IReadOnlyCollection et je résous ce problème dans une requête linq :

var list1 = list.Where(i => !list2.Contains(i)).ToList();
var list2 = list2.Where(i => !list.Contains(i)).ToList();

Mais cela ne fonctionne pas aussi bien que je le voudrais. Avez-vous une idée pour rendre cette opération plus rapide et moins gourmande en ressources, car je dois traiter un grand nombre de listes ?

Answer 1

Utilisez Except :

var firstNotSecond = list1.Except(list2).ToList();
var secondNotFirst = list2.Except(list1).ToList();

Je soupçonne qu'il existe des approches qui seraient en fait légèrement plus rapides que cela, mais même cela sera largement plus rapide que votre approche O(N * M).

Answer 2

Méthode Enumerable.SequenceEqual

Détermine si deux séquences sont égales selon un comparateur d'égalité. MS.Docs

Enumerable.SequenceEqual(list1, list2);

Cela fonctionne pour tous les types de données primitives. Si vous souhaitez l'utiliser sur des objets personnalisés, vous devez implémenter la fonction IEqualityComparer

Définit des méthodes pour prendre en charge la comparaison d'objets pour l'égalité.

Interface IEqualityComparer

Définit des méthodes pour prendre en charge la comparaison d'objets pour l'égalité. MS.Docs pour IEqualityComparer

Answer 3

Il serait plus efficace d'utiliser Enumerable.Except :

var inListButNotInList2 = list.Except(list2);
var inList2ButNotInList = list2.Except(list);

Cette méthode est mise en œuvre en utilisant l'exécution différée. Cela signifie que vous pouvez écrire par exemple

var first10 = inListButNotInList2.Take(10);

Elle est également efficace puisqu'elle utilise en interne une Set<T> pour comparer les objets. Il fonctionne en collectant d'abord toutes les valeurs distinctes de la deuxième séquence, puis en diffusant les résultats de la première, en vérifiant qu'ils n'ont pas été vus auparavant.

Answer 4

Si vous voulez que les résultats soient insensible à la casse les éléments suivants fonctionneront :

List<string> list1 = new List<string> { "a.dll", "b1.dll" };
List<string> list2 = new List<string> { "A.dll", "b2.dll" };

var firstNotSecond = list1.Except(list2, StringComparer.OrdinalIgnoreCase).ToList();
var secondNotFirst = list2.Except(list1, StringComparer.OrdinalIgnoreCase).ToList();

firstNotSecond contiendrait b1.dll

secondNotFirst contiendrait b2.dll

Answer 5

using System.Collections.Generic;
using System.Linq;

namespace YourProject.Extensions
{
    public static class ListExtensions
    {
        public static bool SetwiseEquivalentTo<T>(this List<T> list, List<T> other)
            where T: IEquatable<T>
        {
            if (list.Except(other).Any())
                return false;
            if (other.Except(list).Any())
                return false;
            return true;
        }
    }
}

Parfois, il suffit de savoir si deux listes sont différentes, et non pas ce que sont ces différences. Dans ce cas, pensez à ajouter cette méthode d'extension à votre projet. Notez que vos objets listés doivent implémenter IEquatable !

Utilisation :

public sealed class Car : IEquatable<Car>
{
    public Price Price { get; }
    public List<Component> Components { get; }

    ...
    public override bool Equals(object obj)
        => obj is Car other && Equals(other);

    public bool Equals(Car other)
        => Price == other.Price
            && Components.SetwiseEquivalentTo(other.Components);

    public override int GetHashCode()
        => Components.Aggregate(
            Price.GetHashCode(),
            (code, next) => code ^ next.GetHashCode()); // Bitwise XOR
}

Quel que soit le Component est, les méthodes présentées ici pour Car devraient être mis en œuvre de manière presque identique.

Il est très important de noter comment nous avons écrit GetHashCode. Afin d'implémenter correctement IEquatable , Equals et GetHashCode doit opèrent sur les propriétés de l'instance d'une manière logiquement compatible.

Deux listes ayant le même contenu sont toujours des objets différents, et produiront des codes de hachage différents. Puisque nous voulons que ces deux listes soient traitées comme étant égales, nous devons laisser la fonction GetHashCode produire la même valeur pour chacun d'eux. Nous pouvons accomplir cela en déléguant le code de hachage à chaque élément de la liste, et en utilisant le XOR standard par bit pour les combiner tous. XOR est indépendant de l'ordre, donc peu importe que les listes soient triées différemment. Il importe seulement qu'elles ne contiennent que des éléments équivalents.

Note : le nom étrange est pour impliquer le fait que la méthode ne considère pas l'ordre des éléments dans la liste. Si vous vous souciez de l'ordre des éléments de la liste, cette méthode n'est pas pour vous !