Come confrontare due elenchi di grandi dimensioni in modo efficiente in C#?

Question

Ho due elenchi generici con 20.000 e 30.000 oggetti in ciascuna lista.

class Employee 
{ 
    string name; 
    double salary; 
} 

List<Employee> newEmployeeList = List<Employee>() {....} // contains 20,000 objects 
List<Employee> oldEmployeeList = List<Employee>() {....} // contains 30,000 objects 

Le liste possono anche essere ordinate per nome se migliora la velocità.

voglio mettere a confronto queste due liste per scoprire

1. dipendenti il ​​cui nome e stipendio corrispondenza
2. dipendenti il ​​cui nome è corrispondenza, ma non di stipendio

Qual è il modo più veloce per confrontare elenchi di dati così grandi con condizioni sopra?

Answer 1

Vorrei ordinare entrambi gli elenchi newEmployeeList e oldEmployeeList per name - O(n*log(n)). E poi puoi usare l'algoritmo lineare per cercare le corrispondenze. Quindi il totale sarebbe O(n+n*log(n)) se entrambi gli elenchi hanno circa la stessa dimensione. Questo dovrebbe essere più veloce dell'algoritmo "forza bruta" O(n^2).

Answer 2

Uno dei più veloci possibili soluzioni su ordinato liste è l'uso di BinarySearch al fine di trovare un elemento in un altro elenco.

Ma, come mantioned altri, si dovrebbe misurare contro tuoi requisiti di progetto, come le prestazioni spesso tende ad essere una soggettiva cosa .

Answer 3

Si potrebbe creare un dizionario con

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

che darebbe si chiude a O (1) ricerca e una stretta a O (n) il comportamento, se stai cercando i valori da un ciclo sopra l'altro elenco.

(sto dando per scontato che ToDictionary è O (n) che avrebbe senso con un'implementazione dritto in avanti, ma non ho ancora testato questo per essere il caso)

Ciò farebbe per un dritto in avanti algoritmo, e sto pensando che andare sotto O (n) con due liste non ordinate è piuttosto difficile.

Answer 4

Probabilmente raccomanderei che le due liste vengano memorizzate in un Dictionary<string, Employee> in base al nome per iniziare, quindi è possibile scorrere le chiavi in ​​uno e cercare di vedere se esistono e gli stipendi corrispondono nell'altro. Ciò farebbe risparmiare anche il costo di ordinarli successivamente o di metterli in una struttura più efficiente.

Questo è praticamente O (n) - lineare per costruire entrambi i dizionari, lineare per passare attraverso le chiavi e cercare nell'altro. Dal momento che O (n + m + n) si riduce a O (n)

Ma, se è necessario utilizzare List<T> per contenere le liste per altri motivi, si potrebbe anche utilizzare il metodo Join() LINQ, e costruire una nuova lista con un campo Match che ti dice se erano una corrispondenza o mancata corrispondenza ...

 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 
       }); 

È quindi possibile filtrare questo con una clausola Where() per Match o !Match.

Answer 5

Aggiornamento: Presumo (dal titolo della domanda) che i 2 elenchi siano già ordinati. Forse sono memorizzati in un database con un indice cluster o qualcosa del genere. Questa risposta, quindi, si basa su tale assunto.

Ecco un'implementazione con complessità O(n) ed è anche molto veloce, ed è anche piuttosto semplice.
Credo che questa sia una variante di Merge Algorithm.

Ecco l'idea:

1. Inizio enumerazione entrambe le liste
2. confrontare i 2 elementi attuali.
3. Se corrispondono, aggiungi ai risultati.
   Se la prima voce è "più piccola", avanzare alla prima lista.
   Se il secondo elemento è "più piccolo", avanzare nella seconda lista.

Poiché entrambi gli elenchi sono noti per essere ordinati, questo funzionerà molto bene. Questa implementazione presuppone che name sia univoco in ciascuna lista.

var comparer = StringComparer.OrdinalIgnoreCase; 
var namesAndSalaries = new List<Tuple<Employee, Employee>>(); 
var namesOnly = new List<Tuple<Employee, Employee>>(); 

// Create 2 iterators; one for old, one for new: 
using (IEnumerator<Employee> A = oldEmployeeList.GetEnumerator()) { 
    using (IEnumerator<Employee> B = newEmployeeList.GetEnumerator()) { 
     // Start enumerating both: 
     if (A.MoveNext() && B.MoveNext()) { 
      while (true) { 
       int compared = comparer.Compare(A.Current.name, B.Current.name); 
       if (compared == 0) { 
        // Names match 
        if (A.Current.salary == B.Current.salary) { 
         namesAndSalaries.Add(Tuple.Create(A.Current, B.Current)); 
        } else { 
         namesOnly.Add(Tuple.Create(A.Current, B.Current)); 
        } 
        if (!A.MoveNext() || !B.MoveNext()) break; 
       } else if (compared == -1) { 
        // Keep searching A 
        if (!A.MoveNext()) break; 
       } else { 
        // Keep searching B 
        if (!B.MoveNext()) break; 
       } 

      } 
     } 
    } 
}