如何在C#中有效地从另一个中减去一个巨大的列表

Question

我有一个很长的Ids(整数)列表,它代表了我数据库中当前的所有项目:

var idList = GetAllIds();

我还有另一个巨大的通用列表,其中包含要添加到数据库的项目:

List<T> itemsToAdd;

现在,我想删除其Id已经在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这也将从左侧删除所有重复项.即new int[]{1,1,2}.Except(new int[]{2})将导致just {1},第二个1将被删除.但我认为在你的情况下没问题,因为ID通常是唯一的.

Answer 2

暂时转换idList为a HashSet<T>并使用相同的方法,即:

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

它应该快得多

Answer 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.