Как вычесть один огромный список из другого в С#

У меня очень длинный список идентификаторов (целых), которые представляют все элементы, которые в настоящее время находятся в моей базе данных:

var idList = GetAllIds();

У меня также есть еще один огромный общий список с элементами для добавления в базу данных:

List<T> itemsToAdd;

Теперь я хотел бы удалить все элементы из общего списка, Id которого уже находится в idList. В настоящее время idList - это простой массив, и я вычитаю списки следующим образом:

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

Я уверен, что это может быть намного быстрее, поэтому какие типы данных следует использовать для обеих коллекций и что наиболее эффективная практика заключается в их вычитании?

Спасибо!

Ответ 1

Временное преобразование idList в HashSet<T> и использование того же метода, i.e.:

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

он должен быть намного быстрее

Ответ 2

LINQ может помочь:

itemsToAdd.Except(idList)

Ваш код медленный, потому что List<T>.Contains - O(n). Таким образом, ваша общая стоимость составляет O(itemsToAdd.Count*idList.Count).

Вы можете сделать idList в HashSet<T>, который имеет O(1) .Contains. Или просто используйте метод расширения Linq .Except, который сделает это для вас.

Обратите внимание, что .Except также удалит все дубликаты с левой стороны. т.е. новый int[]{1,1,2}.Except(new int[]{2}) приведет к простому {1}, а второй 1 будет удален. Но я предполагаю, что это не проблема в вашем случае, потому что идентификаторы обычно уникальны.

Ответ 3

Предполагая, верны следующие предпосылки:

idList и itemsToAdd могут не содержать повторяющихся значений
вы используете .NET Framework 4.0

вы можете использовать HashSet <T> следующим образом:

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

В соответствии с документацией метод ISet < T.ExceptWith довольно эффективен:

Этот метод является операцией O (n) где n - число элементов в другой параметр.

В вашем случае n - количество элементов в idList.

Ответ 4

Вы должны использовать два HashSet<int> s.
Обратите внимание, что они уникальны и неупорядочены.