如何在C#中有效地从另一个中减去一个巨大的列表
我有一个很长的Ids(整数)列表,它代表了我数据库中当前的所有项目:
var idList = GetAllIds();
我还有另一个巨大的通用列表,其中包含要添加到数据库的项目:
List itemsToAdd;
现在,我想删除ID已经在idList中的通用列表中的所有项目。 目前idList是一个简单的数组,我减去这样的列表:
itemsToAdd.RemoveAll(e => idList.Contains(e.Id));
我很确定它可以快得多,所以我应该为两个集合使用什么数据类型以及减去它们的最有效做法是什么?
谢谢!
暂时将idList
转换为HashSet
并使用相同的方法,即:
items.RemoveAll(e => idListHash.Contains(e.Id));
它应该快得多
LINQ可以提供帮助:
itemsToAdd.Except(idList)
你的代码很慢,因为List
是O(n)
。 所以你的总费用是O(itemsToAdd.Count*idList.Count)
。
您可以将idList设置为具有O(1)
.Contains
的HashSet
。 或者只使用Linq .Except
扩展方法为您完成。
请注意.Except
除了还将删除左侧的所有重复项。 即new int[]{1,1,2}.Except(new int[]{2})
将导致{1}
,第二个1被删除。 但我认为在你的情况下没问题,因为ID通常是唯一的。
假设以下前提是正确的:
-
idList
和itemsToAdd
可能不包含重复值 - 您正在使用.NET Framework 4.0
你可以这样使用HashSet
var itemsToAddSet = new HashSet(itemsToAdd); itemsToAddSet.ExceptWith(idList);
根据文档, ISet
此方法是O(n)操作,其中n是另一个参数中的元素数。
在您的情况下, n
是idList
的项目idList
。
您应该使用两个HashSet
。
请注意,它们是唯一且无序的。