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

Question

我有一个很长的 ID(整数)列表，代表我数据库中当前的所有项目:

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还将删除左侧的所有重复项。即新int[]{1,1,2}.Except(new int[]{2})只会产生 {1}第二个 1 被删除。但我认为这对您来说没有问题，因为 ID 通常是唯一的。