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

Question

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

var idList = GetAllIds();

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

List<T> itemsToAdd;

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

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

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

Спасибо!

Answer 1

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 был удален. Но я предполагаю, что в вашем случае это не проблема, потому что идентификаторы, как правило, уникальны.

Answer 2

Преобразуйте временно idList в HashSet<T> и используйте тот же метод, то есть:

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

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

Answer 3

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

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

вы можете использовать HashSet таким образом:

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

Согласно документации, метод ISet .ExceptWith довольно эффективен:

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

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

Answer 4

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