我有一个非常大的整数列表（大约20亿个元素）和一个索引列表（几千个元素），我需要从第一个列表中删除元素，我目前的方法是循环第二个列表中的所有索引，将每个索引传递给第一个列表的RemoveAt()方法：
indices.Sort();
indices.Reverse();
for (i = 0; i < indices.Count; i++)
{
largeList.RemoveAt(indices[i]);
}但是，大约需要2分钟才能完成，我确实需要执行这个操作快得多，有没有办法优化这个？
我有一个10核的英特尔i9X CPU，所以也许有一些并行处理的方式？
6条答案
按热度按时间0wi1tuuw1#
每次调用
RemoveAt()时，它必须将指定索引之后的每个元素向上移动一个元素，如果在一个非常大的列表中有数千个元素要删除，这将导致许多许多（不必要的）移动。我的想法是，如果你能计算出每个移动的起始索引和长度，你就可以在一个没有重叠移动的单遍中处理列表。这是通过比较索引列表中的相邻元素来完成的。虽然这确实意味着要构建第三个
List<>移动操作来执行，但我希望有最高效的，事先计划好的最小移动策略最终会得到回报（或者可能有一种方法可以做到这一点，而不分配任何目前没有出现在我身上的对象）。在下面的基准测试代码中，您可以看到我的实现
RemoveUsingMoveStrategy()。在test模式下运行下面的启动程序，我们可以看到，当给定索引0、1、5、10、11、15、15时，它和其他答案都产生了正确的结果（重复）、18和19从20-元素List<int>中删除...基准测试说明
List<int>进行基准测试，但是RemoveUsingRemoveAt()--受问题中的代码启发--效率 * 太 * 低，花费的时间太长，所以我只使用了1000万个元素。RemoveUsingRemoveAt()的十亿元素的基准测试，为此，我引入了一个不太幼稚的实现RemoveUsingListCopy()作为比较所有列表大小的基线，顾名思义，它不修改输入列表，而是创建一个应用了删除操作的新列表。DataList和RemovalList），并将var更改为显式类型，以使读者更清楚。RemovalListLocation指示从DataList中的何处移除索引。Beginning、Middle和End，它是从该位置移除的连续RemovalListSize大小的块。Random，它是从一个常量种子生成的RemovalListSize随机、有效、未排序、不保证唯一的索引。为了保持结果简短（呃），我选择只对
Middle和Random的值进行基准测试--认为这将是一个很好的折中方案。基准测试结果
RemoveUsingRemoveAt()是可怕的。不要这样做。RemoveUsingListCopy()始终是最快的，代价是内存使用量加倍。这正好说明了你不应该总是偏爱
List<>而不是一个阵列--除非你需要它的额外功能--因为它并不总是上级的。它隔离了底层阵列，阻止你（没有反射）在它上面使用更高性能的访问方法，比如Array.Copy()和unsafe代码。HashSet<>.Contains()并递增一个索引变量--在较大的列表中确实会伤害它。基准数据
在
benchmark模式下运行本答案后面定义的启动程序，我从BenchmarkDotNet得到这些结果...基准代码
要查看各种实现，请向下滚动三分之一，查找用
[Benchmark()]修饰的方法。这需要
BenchmarkDotNetpackage。启动器代码
RunBenchmark()定义要运行的基准作业的类型以及运行时间。为了在.NET Framework（4.8）上进行基准测试，我必须将以下属性添加到我的.NET Core
.csproj项目文件：laawzig22#
由于源列表的顺序很重要，您可以在列表中向下移动每个项，跳过要删除的索引，然后删除列表的末尾。
更新：获取
RemoveAll的.Net Core源代码，并将其修改为索引列表而不是 predicate 。更新2：优化为尽可能不重复检测。
更新3：简化为在基准测试中使用额外代码的优化。
将
src作为大列表，将removeAtList作为要以某种随机顺序删除的索引，您可以执行以下操作：对于一个10亿个随机整数元素的列表和一个1000 - 3000个随机索引元素的列表，使用这个算法，每次删除只需1.1毫秒，而使用
RemoveAt，每次删除需要232.77毫秒，所以速度快了大约200倍。cigdeys33#
允许这被并行化的一种方式是将列表分成多个片段;也许最初（任意地）分离100万个元素的块。只要每个块保持其自己的计数，您就可以按索引将工作拆分为从不同块的移除（纯粹基于计数），然后并发地进行实际的移除工作。如果你在每个中留下一些备用容量，你也可以更便宜地向中间添加元素，因为您通常只接触一个厚片。随机访问会稍慢，因为您可能需要查看多个厚片计数来确定正确的厚片，但如果厚片计数保持在连续矢量中（而不是针对每个slab），那么在执行此操作时，您应该具有出色的内存缓存命中率。
xxhby3vn4#
这个答案基于这里的其他答案-主要是，我在列表中向上移动元素，正如@Vernou建议的那样（在他们的回答中）和@BACON（在评论中）。这一个终于有表现了（不像我的前几种方法），而且比目前发布的其他解决方案更快，至少在我的测试中-我尝试了OP的
2_000_000_000条目和2_000索引设置-在我的笔记本电脑（i7- 8550U@1.8GHz，16 GB RAM）上运行时间不到10秒：csga3l585#
方法
List.RemoveAt从删除的项复制所有后续项，在您的例子中，每个项复制2，000 * 2，000，000，000次（不是真的，但真的很接近）。解决方案是在已删除项和下一个已删除项之间手动复制项：
lskq00tm6#
如果要从
List中删除多个项，并且无法使用新的List替换List，则最有效的方法是使用RemoveAll方法而不是RemoveAt。RemoveAll只重新排列List的内部状态一次，而不是在每个删除项时重新排列一次。RemoveAll接受为列表中的每个项调用一次的Predicate<T>（大列表）。不幸的是，这个委托没有接收到当前测试项的索引。然而，你 * 可以 * 依赖于了解RemoveAll是如何实现的。源代码显示，这些项是按升序顺序测试的。因此，基于这些知识，你 * 可以 * 从列表中删除选定的索引，非常高效，使用以下三行代码：虽然这种行为没有明确的记录。理论上微软可以在未来的.NET版本中改变
RemoveAll方法的行为，破坏上面的代码。我个人认为这种情况几乎是不可能的，但是如果你想安全起见，你可以使用一个自定义的RemoveAll实现，它有固定的行为，就像这个答案中找到的那样。它也有一个带索引的委托。你可以像这样使用它：