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

Pas pour ce problème, mais pour comparer des listes d'objets identiques et non identiques

public class EquatableList<T> : List<T>, IEquatable<EquatableList<T>> where T : IEquatable<T>
{
    /// <summary>
    /// True, if this contains element with equal property-values
    /// </summary>
    /// <param name="element">element of Type T</param>
    /// <returns>True, if this contains element</returns>
    public new Boolean Contains(T element)
    {
        foreach (T t in this) if (t.Equals(element)) return true;

        return false;
    }

    /// <summary>
    /// True, if list is equal to this
    /// </summary>
    /// <param name="list">list</param>
    /// <returns>True, if instance euqals list</returns>
    public Boolean Equals(EquatableList<T> list)
    {
        if (list == null) return false;

        foreach (T t in this) if (!list.Contains(t)) return false;

        foreach (T t in list) if (!this.Contains(t)) return false;

        return true;

    }
}

}

Answer 2

Essayez de cette façon :

var difList = list1.Where(a => !list2.Any(a1 => a1.id == a.id))
            .Union(list2.Where(a => !list1.Any(a1 => a1.id == a.id)));

Answer 3

Si vous n'avez besoin que d'un résultat combiné, cela fonctionnera aussi :

var set1 = new HashSet<T>(list1);
var set2 = new HashSet<T>(list2);
var areEqual = set1.SetEquals(set2);

où T est le type d'élément de la liste.

Answer 4

Bien que la réponse de Jon Skeet soit un excellent conseil pour la pratique quotidienne avec un nombre d'éléments faible à modéré (jusqu'à quelques millions), ce n'est pas l'approche la plus rapide ni la plus efficace en termes de ressources. Un inconvénient évident est le fait que l'obtention de la différence totale nécessite deux passages sur les données (voire trois si les éléments qui sont égaux sont également intéressants). Il est clair que cela peut être évité par une réimplémentation personnalisée de la fonction Except mais il n'en reste pas moins que la création d'un ensemble de hachage nécessite beaucoup de mémoire et que le calcul des hachages prend du temps.

Pour les très grands ensembles de données (dans les milliards d'éléments), il est généralement utile d'examiner les circonstances particulières. Voici quelques idées qui pourraient vous inspirer : Si les éléments peuvent être comparés (ce qui est presque toujours le cas dans la pratique), il convient alors de trier les listes et d'appliquer l'approche zip suivante :

/// <returns>The elements of the specified (ascendingly) sorted enumerations that are
/// contained only in one of them, together with an indicator,
/// whether the element is contained in the reference enumeration (-1)
/// or in the difference enumeration (+1).</returns>
public static IEnumerable<Tuple<T, int>> FindDifferences<T>(IEnumerable<T> sortedReferenceObjects,
    IEnumerable<T> sortedDifferenceObjects, IComparer<T> comparer)
{
    var refs  = sortedReferenceObjects.GetEnumerator();
    var diffs = sortedDifferenceObjects.GetEnumerator();
    bool hasNext = refs.MoveNext() && diffs.MoveNext();
    while (hasNext)
    {
        int comparison = comparer.Compare(refs.Current, diffs.Current);
        if (comparison == 0)
        {
            // insert code that emits the current element if equal elements should be kept
            hasNext = refs.MoveNext() && diffs.MoveNext();

        }
        else if (comparison < 0)
        {
            yield return Tuple.Create(refs.Current, -1);
            hasNext = refs.MoveNext();
        }
        else
        {
            yield return Tuple.Create(diffs.Current, 1);
            hasNext = diffs.MoveNext();
        }
    }
}

Cela peut par exemple être utilisé de la manière suivante :

const int N = <Large number>;
const int omit1 = 231567;
const int omit2 = 589932;
IEnumerable<int> numberSequence1 = Enumerable.Range(0, N).Select(i => i < omit1 ? i : i + 1);
IEnumerable<int> numberSequence2 = Enumerable.Range(0, N).Select(i => i < omit2 ? i : i + 1);
var numberDiffs = FindDifferences(numberSequence1, numberSequence2, Comparer<int>.Default);

Un benchmarking sur mon ordinateur a donné le résultat suivant pour N = 1M :

Méthode

Moyenne

Erreur

Ecart-type

Ratio

Gen 0

Gen 1

Gen 2

Alloué

DiffLinq

115,19 ms

0,656 ms

0,582 ms

1.00

2800.0000

2800.0000

2800.0000

67110744 B

DiffZip

23,48 ms

0,018 ms

0,015 ms

0.20

-

-

-

720 B

Et pour N = 100M :

Méthode

Moyenne

Erreur

Ecart-type

Ratio

Gen 0

Gen 1

Gen 2

Alloué

DiffLinq

12.146 s

0.0427 s

0.0379 s

1.00

13000.0000

13000.0000

13000.0000

8589937032 B

DiffZip

2.324 s

0.0019 s

0.0018 s

0.19

-

-

-

720 B

Notez que cet exemple bénéficie bien sûr du fait que les listes sont déjà triées et que les entiers peuvent être comparés très efficacement. Mais c'est exactement le but recherché : si vous disposez de circonstances favorables, veillez à les exploiter.

Quelques commentaires supplémentaires : La vitesse de la fonction de comparaison est clairement pertinente pour les performances globales, il peut donc être bénéfique de l'optimiser. La flexibilité de le faire est un avantage de l'approche de zippage. De plus, la parallélisation me semble plus réalisable, même si elle n'est pas facile et ne vaut peut-être pas l'effort et les frais généraux. Néanmoins, un moyen simple d'accélérer le processus d'un facteur 2 environ consiste à diviser les listes en deux moitiés (si cela peut être fait efficacement) et à comparer les parties en parallèle, l'une traitant de l'avant vers l'arrière et l'autre dans l'ordre inverse.

Answer 5

J'ai utilisé ce code pour comparer deux listes qui ont des millions d'enregistrements.

Cette méthode ne prendra pas beaucoup de temps

    //Method to compare two list of string
    private List<string> Contains(List<string> list1, List<string> list2)
    {
        List<string> result = new List<string>();

        result.AddRange(list1.Except(list2, StringComparer.OrdinalIgnoreCase));
        result.AddRange(list2.Except(list1, StringComparer.OrdinalIgnoreCase));

        return result;
    }