Comment comparer efficacement deux grandes listes triées en C#?

Question

Je dispose de deux listes génériques avec 20 000 et 30 000 objets dans chaque liste.

class Employee
{
    string name;
    double salary;
}

List newEmployeeList = List() {....} // contient 20 000 objets
List oldEmployeeList = List() {....} // contient 30 000 objets

Les listes peuvent également être triées par nom si cela améliore la vitesse.

Je veux comparer ces deux listes pour trouver

1. les employés dont le nom et le salaire correspondent
2. les employés dont le nom correspond mais pas le salaire

Quelle est la manière la plus rapide de comparer de telles grandes listes de données avec les conditions ci-dessus?

Answer 1

Je trierais à la fois les listes newEmployeeList et oldEmployeeList par name - O(n*log(n)). Ensuite, vous pouvez utiliser un algorithme linéaire pour rechercher des correspondances. Ainsi, le total serait de O(n+n*log(n)) si les deux listes sont environ de la même taille. Ceci devrait être plus rapide que l'algorithme "brute force" en O(n^2).

Answer 2

Je recommanderais probablement que les deux listes soient stockées dans un Dictionnaire basé sur le nom pour commencer, puis vous pouvez itérer sur les clés dans l'une et chercher pour voir si elles existent et si les salaires correspondent dans l'autre. Cela permettrait également d'éviter les coûts de les trier plus tard ou de les mettre dans une structure plus efficace.

C'est à peu près O(n) - linéaire pour construire les deux dictionnaires, linéaire pour parcourir les clés et chercher dans l'autre. Puisque O(n + m + n) se réduit à O(n)

Mais, si vous devez utiliser List pour contenir les listes pour d'autres raisons, vous pouvez également utiliser la méthode Join() LINQ, et construire une nouvelle liste avec un champ Match qui vous indique s'ils étaient une correspondance ou une discordance...

        var results = newEmpList.Join(
            oldEmpList,
            n => n.Name,
            o => o.Name,
            (n, o) => new 
                { 
                    Name = n.Name, 
                    Salary = n.Salary, 
                    Match = o.Salary == n.Salary 
                });

Ensuite, vous pouvez filtrer ceci avec une clause Where() pour Match ou !Match.

Answer 3

Mise à jour : Je suppose (par le titre de votre question) que les 2 listes sont déjà triées. Peut-être sont-elles stockées dans une base de données avec un index clusterisé ou quelque chose comme ça. Cette réponse repose donc sur cette hypothèse.

Voici une implémentation qui a une complexité de O(n), qui est également très rapide, ET qui est aussi assez simple.
Je crois que c'est une variante de l'algorithme de fusion.

Voici l'idée :

1. Commence à énumérer les deux listes
2. Compare les 2 éléments actuels.
3. Si ils correspondent, ajoutez à vos résultats.
   Si le 1er élément est "plus petit", avancez dans la 1ère liste.
   Si le 2ème élément est "plus petit", avancez dans la 2ème liste.

Puisque les deux listes sont connues pour être triées, cela fonctionnera très bien. Cette implémentation suppose que name est unique dans chaque liste.

var comparer = StringComparer.OrdinalIgnoreCase;
var nomsEtSalaires = new List>();
var nomsSeulement = new List>();

// Créez 2 itérateurs ; un pour l'ancien, un pour le nouveau :
using (IEnumerator A = oldEmployeeList.GetEnumerator()) {
    using (IEnumerator B = newEmployeeList.GetEnumerator()) {
        // Commencez à les énumérer tous les deux :
        if (A.MoveNext() && B.MoveNext()) {
            while (true) {
                int comparé = comparer.Compare(A.Current.name, B.Current.name);
                if (comparé === 0) {
                    // Les noms correspondent
                    if (A.Current.salary == B.Current.salary) {
                        nomsEtSalaires.Add(Tuple.Create(A.Current, B.Current));
                    } else {
                        nomsSeulement.Add(Tuple.Create(A.Current, B.Current));
                    }
                    if (!A.MoveNext() || !B.MoveNext()) break;
                } else if (comparé === -1) {
                    // Continuez de chercher dans A
                    if (!A.MoveNext()) break;
                } else {
                    // Continuez de chercher dans B
                    if (!B.MoveNext()) break;
                }

            }
        }
    }
}

Answer 4

Un des solutions les plus rapides sur les listes triées est l'utilisation de BinarySearch pour trouver un élément dans une autre liste.

Mais comme d'autres l'ont mentionné, vous devriez le mesurer par rapport aux exigences de votre projet, car la performance tend souvent à être une chose subjective.

Answer 5

Vous pourriez créer un dictionnaire en utilisant

var lookupDictionary = list1.ToDictionary(x=>x.name);

Cela vous donnerait une recherche proche de O(1) et un comportement proche de O(n) si vous cherchez des valeurs à partir d'une boucle sur l'autre liste.

(Je suppose ici que ToDictionary est O(n) ce qui aurait du sens avec une implémentation simple, mais je n'ai pas testé pour confirmer que c'est le cas)

Cela ferait un algorithme très simple, et je pense qu'aller en dessous de O(n) avec deux listes non triées est assez difficile.