Cómo restar una lista enorme de otra manera eficiente en C#

Question

tengo una lista muy larga de la identificación (números enteros) que representa todos los elementos que se encuentran actualmente en mi base de datos:

var idList = GetAllIds(); 

También tengo otro gran genérica lista con los elementos a añadir a la base de datos:

List<T> itemsToAdd; 

Ahora, me gustaría eliminar todos los elementos de la lista genérica cuyo ID está ya en la idList. Actualmente idList es una simple matriz y restar las listas de la siguiente manera:

itemsToAdd.RemoveAll(e => idList.Contains(e.Id)); 

Estoy bastante seguro de que podría ser mucho más rápido, por lo que los tipos de datos debería usar tanto para colecciones y lo que es la práctica más eficiente para restarlos?

¡Gracias!

Answer 1

transformar temporalmente idList a un HashSet<T> y utilizar el mismo método, es decir:

items.RemoveAll(e => idListHash.Contains(e.Id)); 

que debería ser mucho más rápido

Answer 2

Debe usar dos HashSet<int> s.
Tenga en cuenta que son únicos y no ordenados.

Answer 3

LINQ podría ayudar:

itemsToAdd.Except(idList) 

Su código es lento porque List<T>.Contains es O(n). Entonces, su costo total es O(itemsToAdd.Count*idList.Count).

Puede hacer idList en un HashSet<T> que tiene O(1).Contains. O simplemente use el método de extensión Linq .Except que lo hace por usted.

Tenga en cuenta que .Except también eliminará todos los duplicados del lado izquierdo. es decir, el nuevo int[]{1,1,2}.Except(new int[]{2}) dará como resultado {1} y el segundo 1 se eliminó. Pero supongo que no es un problema en su caso porque los ID son típicamente únicos.

Answer 4

Suponiendo las siguientes premisas son verdaderas:

• idList y itemsToAdd no puede contener valores duplicados
• está utilizando .NET Framework 4.0

Se puede usar un HashSet<T> esta manera:

var itemsToAddSet = new HashSet(itemsToAdd); 
itemsToAddSet.ExceptWith(idList); 

según la documentación del método ISet<T>.ExceptWith es bastante eficiente:

Este método es un O (n) la operación, donde n es el número de elementos en el otro parámetro.

En su caso n es el número de elementos en idList.