C#中待处理列表多数元素已存在时的高效移除方案咨询

你的原始代码性能差的核心原因是嵌套遍历的时间复杂度太高：Where遍历pending的每一条记录（60万次），每次又要遍历整个posted列表去匹配ID，总时间复杂度是O(m*n)，这种量级下必然会出现性能瓶颈。

最直接的优化方式是用HashSet存储posted的ID，利用其O(1)的查找效率替代Any的线性遍历：

// 提取posted的ID到HashSet，仅需遍历posted一次
var postedIdSet = new HashSet<int>(posted.Select(item => item.ID));
// 过滤pending，每条记录的ID查找仅需O(1)时间
pending = pending.Where(p => !postedIdSet.Contains(p.ID)).ToList();

为什么这个方案更快？ #

HashSet基于哈希表实现，查找元素的平均时间复杂度是O(1)，整个流程的总时间复杂度降到了O(m + n)（m是pending的元素数，n是posted的元素数），对于几十万级别的数据，性能会有数量级的提升。

额外说明 #

如果你的posted列表是从数据库查询的IQueryable对象，也可以直接使用Contains方法，EF会自动将其转换为SQL的IN子句，让数据库层面完成过滤，同样能获得很好的性能：

var postedIds = posted.Select(item => item.ID).ToList();
pending = pending.Where(p => !postedIds.Contains(p.ID)).ToList();

不过这种方式仅适用于EF等ORM场景，内存列表的最优解还是HashSet。

内容的提问来源于stack exchange，提问作者Rick