¿Cómo se pueden comparar dos listas grandes ordenadas de manera eficiente en C#?

Question

Tengo dos listas genéricas con 20,000 y 30,000 objetos en cada 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 

Las listas también pueden ordenarse por nombre si mejora la velocidad.

quiero comparar estas dos listas para averiguar

1. empleados cuyo nombre y salario de referencia
2. empleados cuyo nombre se emparejan pero no salariales

¿Cuál es la manera más rápida para comparar tales grandes listas de datos con las condiciones anteriores?

Answer 1

Ordenaría las listas de newEmployeeList y oldEmployeeList por name - O(n*log(n)). Y luego puedes usar el algoritmo lineal para buscar coincidencias. Entonces, el total sería O(n+n*log(n)) si ambas listas son aproximadamente del mismo tamaño. Esto debería ser más rápido que O(n^2) algoritmo de "fuerza bruta".

Answer 2

Uno de los más rápidos posibles soluciones en ordenados listas es el uso de BinarySearch con el fin de encontrar un elemento en otra lista.

Pero como mantioned otros, se debe medir contra sus necesidades del proyecto, como el rendimiento a menudo tiende a ser una cosa subjetiva.

Answer 3

Se puede crear un diccionario utilizando

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

que daría a cerrar a O (1) las operaciones de búsqueda y una cerca de O (n) el comportamiento si usted está mirando hacia arriba valores de un bucle sobre la otra lista.

(estoy asumiendo aquí que ToDictionary es O (n), que tendría sentido con una aplicación recta hacia adelante, pero no he probado que esto sea el caso)

Esto haría para un muy sencillo algoritmo, y estoy pensando en ir por debajo de O (n) con dos listas sin clasificar es bastante difícil.

Answer 4

Probablemente recomendaría que las dos listas se almacenen en un Dictionary<string, Employee> basado en el nombre para comenzar, luego puede iterar sobre las claves en una y buscarlas para ver si existen y los sueldos coinciden en la otra. Esto también ahorraría el costo de clasificarlos más tarde o ponerlos en una estructura más eficiente.

Esto es casi O (n) - lineal para construir ambos diccionarios, lineal para ir a través de las teclas y búsqueda en el otro. Desde O (n + m + n) se reduce a O (n)

Pero, si debe utilizar List<T> para mantener las listas por otras razones, se podría también utilizar el método Join() LINQ, y construir una nueva lista con un campo Match que le dice si coinciden o no coinciden ...

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

podrá filtrar esto con una cláusula de Where()Match o !Match.

Answer 5

Actualización: Supongo (por el título de su pregunta) que las 2 listas ya están ordenadas. Quizás estén almacenados en una base de datos con un índice agrupado o algo así. Esta respuesta, por lo tanto, se basa en esa suposición.

Aquí hay una implementación que tiene O(n) complejidad, y también es muy rápida, Y es bastante simple también.
Creo que esta es una variante del Merge Algorithm.

Aquí es la idea:

1. iniciar la enumeración de las dos listas
2. comparar el 2 artículos actuales.
3. Si coinciden, agrega a tus resultados.
   Si el primer elemento es "más pequeño", avance la primera lista.
   Si el 2º elemento es "más pequeño", avance la 2ª lista.

Como se sabe que ambas listas están ordenadas, esto funcionará muy bien. Esta implementación asume que name es único en cada 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; 
       } 

      } 
     } 
    } 
}