C# forma más eficiente de la comparación de dos colecciones

Question

tengo dos colecciones

List<Car> currentCars = GetCurrentCars(); 
List<Car> newCars = GetNewCars(); 

que no quiero utilizar bucle foreach o algo porque creo que debería ser mucho mejor forma de hacer esto.

Busco manera más eficiente para comparar este colecciones y para obtener resultados:

1. Lista de los coches que están en newcars ​​y no en currentCars
2. Lista de coches que no están en newcars ​​y en currentCars

Type Car tiene la propiedad int Id.

había una respuesta, que ya ha sido borrada diciendo Lo que quiero decir diciendo eficiente: menos código, menos la mecánica, y los casos más legibles

Así que pensar de esta manera lo que es los casos que he?

¿Qué sería menos código, menos mecánica y más casos legibles?

Answer 1

Puede utilizar Except:

var currentCarsNotInNewCars = currentCars.Except(newCars); 
var newCarsNotInCurrentCars = newCars.Except(currentCars); 

Pero esto no tiene ninguna ventaja de rendimiento sobre la solución foreach. Simplemente se ve más limpio.
Además, tenga en cuenta que debe implementar IEquatable<T> para su clase Car, por lo que la comparación se realiza en la ID y no en la referencia.

Performancewise, un mejor enfoque sería no utilizar un List<T> sino un Dictionary<TKey, TValue> con el identificador como la clave:

var currentCarsDictionary = currentCars.ToDictionary(x => x.ID); 
var newCarsDictionary = newCars.ToDictionary(x => x.ID); 

var currentCarsNotInNewCars = 
    currentCarsDictionary.Where(x => !newCarsDictionary.ContainsKey(x.Key)) 
         .Select(x => x.Value); 

var newCarsNotInCurrentCars = 
    newCarsDictionary.Where(x => !currentCarsDictionary.ContainsKey(x.Key)) 
        .Select(x => x.Value); 

Answer 2

Usted puede hacerlo de esta manera:

// 1) List of cars in newCars and not in currentCars 
var newButNotCurrentCars = newCars.Except(currentCars); 

// 2) List of cars in currentCars and not in newCars 
var currentButNotNewCars = currentCars.Except(newCars); 

Los usos de código el método de extensión Enumerable.Except (disponible en .Net 3.5 y más).

Creo que esto cumple sus criterios de "menos código, menos mecánica y más legible".

Answer 3

Anularía el Equals de Car para comparar por id y luego podría usar el método de extensión IEnumerable.Except. Si no puede anular el Equals, puede crear su propio IEqualityComparer<Car> que compare dos autos por identificación.

class CarComparer : IEqualityComparer<Car> 
{ 
    public bool Equals(Car x, Car y) 
    { 
     return x != null && y != null && x.Id == y.Id; 
    } 

    public int GetHashCode(Car obj) 
    { 
     return obj == null ? 0 : obj.Id; 
    } 
} 

Answer 4

Puede utilizar LINQ ...

 List<Car> currentCars = new List<Car>(); 
     List<Car> newCars = new List<Car>(); 

     List<Car> currentButNotNew = currentCars.Where(c => !newCars.Contains(c)).ToList(); 
     List<Car> newButNotCurrent = newCars.Where(c => !currentCars.Contains(c)).ToList(); 

... pero no se deje engañar.Puede ser menos código para usted, pero definitivamente habrá algunos bucles en alguna parte

EDIT: No nos dimos cuenta que había un método Excepto :(

Answer 5

Si se inicia con ellos en HashSet s que pueda utilizar el método Except.

HashSet<Car> currentCars = GetCurrentCars(); 
HashSet<Car> newCars = GetNewCars(); 

currentCars.Except(newCars); 
newCars.Except(currentCars); 

sería mucho más rápido w/un conjunto de una lista. (Bajo el capó una lista sólo está haciendo un foreach, conjuntos pueden ser optimizados).

Answer 6

Si' buscando eficiencia, implemente IComparable en Cars (s) describiendo su identificación única) y use una SortedList. Luego puede recorrer sus colecciones y evaluar sus cheques en O (n). Esto, por supuesto, tiene un costo adicional para las inserciones de la Lista para mantener la naturaleza ordenada.

Answer 7

Puede copiar la lista más pequeña en una colección basada en una tabla hash como HashSet o Dictionary y luego iterar sobre la segunda lista y verificar si el elemento existe en la tabla hash.

esto reducirá el tiempo de O (N^2) en el caso forense ingenuo dentro de foreach a O (N).

Esto es lo mejor que puede hacer sin saber más acerca de las listas (es posible que pueda hacer un pequeño mejor si las listas están ordenadas, por ejemplo, pero, dado que tiene que "tocar" cada automóvil al menos una vez para verificar si está en la nueva lista de automóviles, nunca podrá hacerlo mejor que O (N))

Answer 8

Si una comparación de la propiedad de Id es suficiente para decir si un automóvil es igual a otro, para evitar algunos tipo de bucle, puede anular la Lista con su propia clase que realiza un seguimiento de los elementos y utiliza el IEqualityComparer en toda la colección, como este:

class CarComparer : IList<Car>, IEquatable<CarComparer> 
{ 
    public bool Equals(CarComparer other) 
    { 
     return object.Equals(GetHashCode(),other.GetHashCode()); 
    } 

    public override int GetHashCode() 
    { 
     return _runningHash; 
    } 

    public void Insert(int index, Car item) 
    { 
     // Update _runningHash here 
     throw new NotImplementedException(); 
    } 

    public void RemoveAt(int index) 
    { 
     // Update _runningHash here 
     throw new NotImplementedException(); 
    } 

    // More IList<Car> Overrides .... 
} 

Luego, solo tiene que anular Add, Remove, etc. y cualquier otro método que pueda afectar los elementos de la lista. Luego puede mantener una variable privada que es un hash de algún tipo de ID de los elementos en la lista. Al anular sus métodos Equals, puede simplemente comparar esta variable privada. No es el enfoque más limpio por el momento (ya que tiene que mantenerse al día con su variable hash), pero dará como resultado que no tenga que pasar para hacer una comparación. Si fuera yo, simplemente usaría Linq como algunos mencionaron aquí ...