那些遇到过的问题

如何从非常大的列表中按索引有效地删除元素？

N K*_*N K 26 .net c# performance list generic-list

我有一个非常大的整数列表（大约 20 亿个元素）和一个带有索引（几千个元素）的列表，我需要从第一个列表中删除元素。我目前的方法是遍历第二个列表中的所有索引，将每个索引传递给RemoveAt()第一个列表的方法：

indices.Sort();
indices.Reverse();
for (i = 0; i < indices.Count; i++)
{
    largeList.RemoveAt(indices[i]);
}
Run Code Online (Sandbox Code Playgroud)

但是，大约需要 2 分钟才能完成。我真的需要更快地执行此操作。有没有办法优化这个？

我有一个带有 10 个内核的 Intel i9X CPU，所以也许是某种并行处理方式？

BAC*_*CON 18

每次RemoveAt()调用它都必须将指定索引之后的每个元素向上移动一个元素。如果在一个非常大的列表中有数千个元素要删除，那将导致很多很多（不必要的）移动。

我的想法是，如果您可以计算每个移动的开始索引和长度，您就可以一次处理列表而没有重叠移动。这是通过比较要删除的索引列表中的相邻元素来完成的。虽然这确实意味着要构建三分之一List<>的移动操作来执行，但我希望预先计划的最有效、最小的移动策略最终会得到回报（或者也许有一种方法可以在不分配任何当前未分配的对象的情况下做到这一点）不是发生在我身上）。

您可以RemoveUsingMoveStrategy()在下面的基准代码中看到我的实现。在test模式下运行下面的启动程序，我们可以看到它 - 以及其他答案 - 当给定索引0, 1, 5, 10, 11, 15, 15(repeated), 18, 和19to remove from a 20-element List<int>...

PS> dotnet run --configuration release --framework netcoreapp3.1 -- test
[剪辑]
RemoveUsingMoveStrategy():
        元素：{ 2, 3, 4, 6, 7, 8, 9, 12, 13, 14, 16, 17 }
           数：12
        序列：等于控制列表
        持续时间：3.95 毫秒
        返回：输入列表
[剪辑]

基准说明

  • 这是我打算对一个数十亿元的基准List<int>，但RemoveUsingRemoveAt()-在这个问题的代码启发-是如此低效的，它是时间太长了，所以我只去了10万台。

  • 我仍然希望运行一个十亿元素的基准测试，排除RemoveUsingRemoveAt(). 出于这个原因，我引入了一个不太天真的实现，称为RemoveUsingListCopy()作为比较所有列表大小的基线。顾名思义，它不会修改输入列表，而是创建一个应用了删除的新列表。

  • 由于并非所有实现都要求要删除的索引列表是唯一的和/或排序的，因此我认为最公平的基准测试方法是在方法需要的基准时间中包含该开销。

  • 我对其他答案中的代码所做的唯一其他更改是利用基准测试的列表（DataList和RemovalList），并从 更改var为显式类型，以便读者清晰。

  • RemovalListLocation指示从何处DataList删除in索引。

    • 对于Beginning, Middle,End它是RemovalListSize从该位置移除的连续大小的块。
    • 因为Random它是RemovalListSize随机的、有效的、未排序的、不保证唯一的索引，它是从一个恒定的种子生成的。

    为了保持结果简短（呃），我选择只对Middle- 认为这将是一个很好的中间道路妥协 - 和Random价值观进行基准测试。

基准测试结果

  • RemoveUsingRemoveAt()是可怕的。不要那样做。

  • 对于较小的列表，RemoveUsingListCopy()始终是最快的，但代价是内存使用量加倍。

  • 对于更大的列表，Vernou 的答案至少是其他答案的 5 倍，代价是依赖于实现细节。

    这只是表明您不必总是偏爱List<>数组——除非您需要它的附加功能——因为它并不总是优越的。它使用更高性能的访问方法等绝缘底层阵列，防止你（无反射）Array.Copy()和unsafe在其上的代码。

  • Theodor Zoulias 的回答在较小的列表中表现良好，但我认为必须“接触”所有 1000 万个索引——每个索引都调用HashSet<>.Contains()并增加一个索引变量——对于较大的列表确实会伤害它。

  • 其余的实现（包括我的）具有大致相同的性能：不是最好的，但仍然很好。

基准数据

在benchmark模式下运行此答案中稍后定义的启动程序，我从BenchmarkDotNet...

PS> dotnet run --configuration release --framework netcoreapp3.1 -- benchmark
[剪辑]
// * 概括 *

BenchmarkDotNet=v0.12.1，操作系统=Windows 10.0.19041.450 (2004/?/20H1)
Intel Core i7 CPU 860 2.80GHz (Nehalem)，1 个 CPU，8 个逻辑核心和 4 个物理核心
.NET 核心 SDK=3.1.401
  [主机] : .NET Core 3.1.7 (CoreCLR 4.700.20.36602, CoreFX 4.700.20.37001), X64 RyuJIT
  MediumRun : .NET Framework 4.8 (4.8.4200.0), X64 RyuJIT

Job=MediumRun InvocationCount=1 IterationCount=15  
LaunchCount=2 UnrollFactor=1 WarmupCount=10  

| 方法 | 运行时 | 数据列表大小 | 删除列表大小 | 删除列表位置 | 意思 | 错误 | 标准偏差 | 中位数 | 比率 | 比率SD |
|------------------------------ |-------------- |--- ---------- |---------------- |-------------------- |- --------------:|--------------:|--------------:|-- -------------:|------:|--------:|
| RemoveUsingListCopy | .NET 4.8 | 10000 | 2000 | 随机 | 379.9 ?s | 15.93 ?s | 23.36 ?s | 380.4 ?s | 1.00 | 0.00 |
| RemoveUsingRemoveAt | .NET 4.8 | 10000 | 2000 | 随机 | 1,463.7 ?s | 93.79 ?s | 137.47 ?s | 1,434.7 ?s | 3.87 | 0.41 |
| RemoveUsingMoveStrategy | .NET 4.8 | 10000 | 2000 | 随机 | 635.9 ?s | 19.77 ?s | 29.60 ?s | 624.0 ?s | 1.67 | 0.14 |
| Answer63496225_TheodorZoulias | .NET 4.8 | 10000 | 2000 | 随机 | 372.1 ?s | 11.52 ?s | 16.15 ?s | 373.8 ?s | 0.99 | 0.07 |
| Answer63496768_CoolBots | .NET 4.8 | 10000 | 2000 | 随机 | 594.5 ?s | 25.13 ?s | 36.03 ?s | 593.1?s | 1.57 | 0.12 |
| Answer63495657_NetMage | .NET 4.8 | 10000 | 2000 | 随机 | 618.8 ?s | 17.53 ?s | 23.99 ?s | 622.4 ?s | 1.65 | 0.13 |
| Answer63496256_Vernou | .NET 4.8 | 10000 | 2000 | 随机 | 645.6 ?s | 27.28 ?s | 39.99 ?s | 632.2 ?s | 1.71 | 0.16 |
| | | | | | | | | | | |
| RemoveUsingListCopy | .NET 核心 3.1 | 10000 | 2000 | 随机 | 391.5 ?s | 10.39 ?s | 15.55 ?s | 391.6 ?s | 1.00 | 0.00 |
| RemoveUsingRemoveAt | .NET 核心 3.1 | 10000 | 2000 | 随机 | 1,402.2 ?s | 44.20 ?s | 64.80 ?s | 1,407.6 ?s | 3.59 | 0.21 |
| RemoveUsingMoveStrategy | .NET 核心 3.1 | 10000 | 2000 | 随机 | 557.9 ?s | 19.73 ?s | 27.00 ?s | 557.2 ?s | 1.43 | 0.10 |
| Answer63496225_TheodorZoulias | .NET 核心 3.1 | 10000 | 2000 | 随机 | 424.3 ?s | 20.90 ?s | 29.30 ?s | 424.2 ?s | 1.09 | 0.09 |
| Answer63496768_CoolBots | .NET 核心 3.1 | 10000 | 2000 | 随机 | 535.0 ?s | 19.37 ?s | 27.16 ?s | 537.1?s | 1.37 | 0.08 |
| Answer63495657_NetMage | .NET 核心 3.1 | 10000 | 2000 | 随机 | 557.7 ?s | 18.73 ?s | 25.63 ?s | 550.0 ?s | 1.43 | 0.09 |
| Answer63496256_Vernou | .NET 核心 3.1 | 10000 | 2000 | 随机 | 554.2 ?s | 13.82 ?s | 18.45 ?s | 554.0 ?s | 1.42 | 0.07 |
| | | | | | | | | | | |
| RemoveUsingListCopy | .NET 4.8 | 10000 | 2000 | 中 | 221.6 ?s | 7.25 ?s | 10.63 ?s | 222.5 ?s | 1.00 | 0.00 |
| RemoveUsingRemoveAt | .NET 4.8 | 10000 | 2000 | 中 | 1,195.3 ?s | 20.01 ?s | 28.69 ?s | 1,187.7 ?s | 5.42 | 0.30 |
| RemoveUsingMoveStrategy | .NET 4.8 | 10000 | 2000 | 中 | 405.0 ?s | 13.65 ?s | 19.14 ?s | 410.7 ?s | 1.83 | 0.10 |
| Answer63496225_TheodorZoulias | .NET 4.8 | 10000 | 2000 | 中 | 206.3 ?s | 8.62 ?s | 12.09 ?s | 204.9 ?s | 0.94 | 0.08 |
| Answer63496768_CoolBots | .NET 4.8 | 10000 | 2000 | 中 | 427.5 ?s | 15.56 ?s | 22.81 ?s | 435.4 ?s | 1.93 | 0.13 |
| Answer63495657_NetMage | .NET 4.8 | 10000 | 2000 | 中 | 405.4 ?s | 13.80 ?s | 19.35 ?s | 403.8 ?s | 1.84 | 0.11 |
| Answer63496256_Vernou | .NET 4.8 | 10000 | 2000 | 中 | 413.9 ?s | 15.26 ?s | 20.89 ?s | 419.8 ?s | 1.87 | 0.12 |
| | | | | | | | | | | |
| RemoveUsingListCopy | .NET 核心 3.1 | 10000 | 2000 | 中 | 235.2 ?s | 10.73 ?s | 15.73 ?s | 236.2 ?s | 1.00 | 0.00 |
| RemoveUsingRemoveAt | .NET 核心 3.1 | 10000 | 2000 | 中 | 1,345.6 ?s | 32.07 ?s | 43.90 ?s | 1,352.7 ?s | 5.77 | 0.41 |
| RemoveUsingMoveStrategy | .NET 核心 3.1 | 10000 | 2000 | 中 | 324.0 ?s | 4.92 ?s | 7.05 ?s | 326.6 ?s | 1.39 | 0.09 |
| Answer63496225_TheodorZoulias | .NET 核心 3.1 | 10000 | 2000 | 中 | 262.9 ?s | 6.18 ?s | 9.06 ?s | 265.4 ?s | 1.12 | 0.08 |
| Answer63496768_CoolBots | .NET 核心 3.1 | 10000 | 2000 | 中 | 333.6 ?s | 10.14 ?s | 13.87 ?s | 340.9 ?s | 1.43 | 0.11 |
| Answer63495657_NetMage | .NET 核心 3.1 | 10000 | 2000 | 中 | 313.5 ?s | 9.05 ?s | 12.69 ?s | 310.5 ?s | 1.34 | 0.11 |
| Answer63496256_Vernou | .NET 核心 3.1 | 10000 | 2000 | 中 | 332.3?s | 6.70 ?s | 8.95 ?s | 331.9 ?s | 1.43 | 0.09 |
| | | | | | | | | | | |
| RemoveUsingListCopy | .NET 4.8 | 10000000 | 2000 | 随机 | 253,977.1 ?s | 2,721.70 ?s | 3,989.43 ?s | 253,809.0 ?s | 1.00 | 0.00 |
| RemoveUsingRemoveAt | .NET 4.8 | 10000000 | 2000 | 随机 | 5,191,083.4 ?s | 13,200.66 ?s | 18,931.99 ?s | 5,187,162.3 ?s | 20.43 | 0.34 |
| RemoveUsingMoveStrategy | .NET 4.8 | 10000000 | 2000 | 随机 | 65,365.4 ?s | 422.41 ?s | 592.16 ?s | 65,307.3 ?s | 0.26 | 0.00 |
| Answer63496225_TheodorZoulias | .NET 4.8 | 10000000 | 2000 | 随机 | 240,584.4 ?s | 3,687.89 ?s | 5,048.03 ?s | 244,336.1 ?s | 0.95 | 0.02 |
| Answer63496768_CoolBots | .NET 4.8 | 10000000 | 2000 | 随机 | 54,168.4 ?s | 1,001.37 ?s | 1,436.14 ?s | 53,390.3 ?s | 0.21 | 0.01 |
| Answer63495657_NetMage | .NET 4.8 | 10000000 | 2000 | 随机 | 72,501.4 ?s | 452.46 ?s | 634.29 ?s | 72,161.2 ?s | 0.29 | 0.00 |
| Answer63496256_Vernou | .NET 4.8 | 10000000 | 2000 | 随机 | 5,814.0 ?s | 89.71 ?s | 128.67 ?s | 5,825.3 ?s | 0.02 | 0.00 |
| | | | | | | | | | | |
| RemoveUsingListCopy | .NET 核心 3.1 | 10000000 | 2000 | 随机 | 239,784.0 ?s | 2,721.35 ?s | 3,902.88 ?s | 241,125.5 ?s | 1.00 | 0.00 |
| RemoveUsingRemoveAt | .NET 核心 3.1 | 10000000 | 2000 | 随机 | 5,538,337.5 ?s | 353,505.30 ?s | 495,565.06 ?s | 5,208,226.1 ?s | 23.12 | 2.15 |
| RemoveUsingMoveStrategy | .NET 核心 3.1 | 10000000 | 2000 | 随机 | 33,071.8 ?s | 103.80 ?s | 138.57 ?s | 33,030.5 ?s | 0.14 | 0.00 |
| Answer63496225_TheodorZoulias | .NET 核心 3.1 | 10000000 | 2000 | 随机 | 240,825.5 ?s | 851.49 ?s | 1,248.11 ?s | 240,520.9 ?s | 1.00 | 0.02 |
| Answer63496768_CoolBots | .NET 核心 3.1 | 10000000 | 2000 | 随机 | 26,265.0 ?s | 90.76 ?s | 124.23 ?s | 26,253.0 ?s | 0.11 | 0.00 |
| Answer63495657_NetMage | .NET 核心 3.1 | 10000000 | 2000 | 随机 | 48,670.6 ?s | 581.51 ?s | 833.99 ?s | 48,303.0 ?s | 0.20 | 0.00 |
| Answer63496256_Vernou | .NET 核心 3.1 | 10000000 | 2000 | 随机 | 5,905.5 ?s | 96.27 ?s | 131.78 ?s | 5,915.1 ?s | 0.02 | 0.00 |
| | | | | | | | | | | |
| RemoveUsingListCopy | .NET 4.8 | 10000000 | 2000 | 中 | 153,776.2 ?s | 2,454.90 ?s | 3,674.38 ?s | 152,872.0 ?s | 1.00 | 0.00 |
| RemoveUsingRemoveAt | .NET 4.8 | 10000000 | 2000 | 中 | 5,245,952.0 ?s | 13,845.58 ?s | 20,294.67 ?s | 5,252,922.4 ?s | 34.10 | 0.81 |
| RemoveUsingMoveStrategy | .NET 4.8 | 10000000 | 2000 | 中 | 33,233.6 ?s | 110.33 ?s | 158.24 ?s | 33,217.3 ?s | 0.22 | 0.01 |
| Answer63496225_TheodorZoulias | .NET 4.8 | 10000000 | 2000 | 中 | 128,949.8 ?s | 560.72 ?s | 804.17 ?s | 128,724.9 ?s | 0.84 | 0.02 |
| Answer63496768_CoolBots | .NET 4.8 | 10000000 | 2000 | 中 | 48,965.1 ?s | 70.75 ?s | 94.45 ?s | 48,957.3 ?s | 0.32 | 0.01 |
| Answer63495657_NetMage | .NET 4.8 | 10000000 | 2000 | 中 | 32,641.5 ?s | 66.85 ?s | 91.51 ?s | 32,610.0 ?s | 0.21 | 0.01 |
| Answer63496256_Vernou | .NET 4.8 | 10000000 | 2000 | 中 | 2,982.2 ?s | 29.47 ?s | 41.31 ?s | 2,961.9 ?s | 0.02 | 0.00 |
| | | | | | | | | | | |
| RemoveUsingListCopy | .NET 核心 3.1 | 10000000 | 2000 | 中 | 144,208.7 ?s | 2,035.88 ?s | 2,984.16 ?s | 142,693.2 ?s | 1.00 | 0.00 |
| RemoveUsingRemoveAt | .NET 核心 3.1 | 10000000 | 2000 | 中 | 5,235,957.7 ?s | 13,674.19 ?s | 20,043.46 ?s | 5,241,536.1 ?s | 36.32 | 0.78 |
| RemoveUsingMoveStrategy | .NET 核心 3.1 | 10000000 | 2000 | 中 | 16,547.3 ?s | 72.72 ?s | 101.95 ?s | 16,520.7 ?s | 0.11 | 0.00 |
| Answer63496225_TheodorZoulias | .NET 核心 3.1 | 10000000 | 2000 | 中 | 137,218.2 ?s | 716.45 ?s | 980.69 ?s | 137,027.0 ?s | 0.95 | 0.02 |
| Answer63496768_CoolBots | .NET 核心 3.1 | 10000000 | 2000 | 中 | 23,728.5 ?s | 79.84 ?s | 111.93 ?s | 23,689.9 ?s | 0.16 | 0.00 |
| Answer63495657_NetMage | .NET 核心 3.1 | 10000000 | 2000 | 中 | 17,298.3 ?s | 216.46 ?s | 310.44 ?s | 17,165.5 ?s | 0.12 | 0.00 |
| Answer63496256_Vernou | .NET 核心 3.1 | 10000000 | 2000 | 中 | 2,999.7 ?s | 85.78 ?s | 123.03 ?s | 2,957.1 ?s | 0.02 | 0.00 |
[剪辑]

基准代码

要查看各种实现，请向下滚动三分之一并查找用 修饰的方法[Benchmark()]。

这需要BenchmarkDotNet包.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using BenchmarkDotNet.Attributes;

namespace SO63495264
{
    public class Benchmarks
    {
        public enum RemovalLocation
        {
            Random,
            Beginning,
            Middle,
            End
        }

        [Params(10_000, 10_000_000)]
        public int DataListSize
        {
            get; set;
        }

        [Params(2_000)]
        public int RemovalListSize
        {
            get; set;
        }

        //[ParamsAllValues()]
        [Params(RemovalLocation.Random, RemovalLocation.Middle)]
        public RemovalLocation RemovalListLocation
        {
            get; set;
        }

        public List<int> DataList
        {
            get;
            set;
        }

        public IReadOnlyList<int> RemovalList
        {
            get;
            set;
        }

        [GlobalSetup()]
        public void GlobalSetup()
        {
            IEnumerable<int> removalIndices;

            if (RemovalListLocation == RemovalLocation.Random)
            {
                // Pass a constant seed so the same indices get generated for every run
                Random random = new Random(12345);

                removalIndices = Enumerable.Range(0, RemovalListSize)
                    .Select(i => random.Next(DataListSize));
            }
            else
            {
                int removalSegmentOffset = RemovalListLocation switch {
                    RemovalLocation.Beginning => 0,
                    RemovalLocation.Middle => (DataListSize - RemovalListSize) / 2,
                    RemovalLocation.End => DataListSize - RemovalListSize,
                    _ => throw new Exception($"Unexpected {nameof(RemovalLocation)} enumeration value {RemovalListLocation}.")
                };

                removalIndices = Enumerable.Range(removalSegmentOffset, RemovalListSize);
            }

            // For efficiency, create a single List<int> to be reused by all iterations for a given set of parameters
            DataList = new List<int>(DataListSize);
            RemovalList = removalIndices.ToList().AsReadOnly();
        }

        [IterationSetup()]
        public void IterationSetup()
        {
            // Each iteration could modify DataList, so repopulate its elements for the
            // next iteration.  DataList is either new or has been Clear()ed by IterationCleanup().
            for (int i = 0; i < DataListSize; i++)
                DataList.Add(i);
        }

        [IterationCleanup()]
        public void IterationCleanup()
        {
            DataList.Clear();
        }

        [GlobalCleanup()]
        public void GlobalCleanup()
        {
            // Force collection of the List<> for the current set of parameters
            int generation = GC.GetGeneration(DataList);

            DataList = null;
            GC.Collect(generation, GCCollectionMode.Forced, true);
        }

        [Benchmark(Baseline = true)]
        public List<int> RemoveUsingListCopy()
        {
            HashSet<int> removalSet = RemovalList.ToHashSet();
            List<int> newList = new List<int>(DataList.Count - removalSet.Count);

            for (int index = 0; index < DataList.Count; index++)
                if (!removalSet.Contains(index))
                    newList.Add(DataList[index]);

            return newList;
        }

        // Based on Stack Overflow question 63495264
        // /sf/ask/4444668511/
        [Benchmark()]
        public List<int> RemoveUsingRemoveAt()
        {
            // The collection of indices to remove must be in decreasing order
            // with no duplicates; all are assumed to be in-range for DataList
            foreach (int index in RemovalList.Distinct().OrderByDescending(i => i))
                DataList.RemoveAt(index);

            return DataList;
        }

        // From Stack Overflow answer 63498191
        // /sf/answers/4444873401/
        [Benchmark()]
        public List<int> RemoveUsingMoveStrategy()
        {
            // The collection of indices to remove must be in increasing order
            // with no duplicates; all are assumed to be in-range for DataList
            int[] coreIndices = RemovalList.Distinct().OrderBy(i => i).ToArray();
            List<(int startIndex, int count, int distance)> moveOperations
                = new List<(int, int, int)>();

            int candidateIndex;
            for (int i = 0; i < coreIndices.Length; i = candidateIndex)
            {
                int currentIndex = coreIndices[i];
                int elementCount = 1;

                // Merge removal of consecutive indices into one operation
                while ((candidateIndex = i + elementCount) < coreIndices.Length
                    && coreIndices[candidateIndex] == currentIndex + elementCount
                )
                {
                    elementCount++;
                }

                int nextIndex = candidateIndex < coreIndices.Length
                    ? coreIndices[candidateIndex]
                    : DataList.Count;
                int moveCount = nextIndex - currentIndex - elementCount;

                // Removing one or more elements from the end of the
                // list will result in a no-op, 0-length move; omit it
                if (moveCount > 0)
                {
                    moveOperations.Add(
                        (
                            startIndex: currentIndex + elementCount,
                            count: moveCount,
                            distance: i + elementCount
                        )
                    );
                }
            }

            // Perform the element moves
            foreach ((int startIndex, int count, int distance) in moveOperations)
            {
                for (int offset = 0; offset < count; offset++)
                {
                    int sourceIndex = startIndex + offset;
                    int targetIndex = sourceIndex - distance;

                    DataList[targetIndex] = DataList[sourceIndex];
                }
            }

            // "Trim" the number of removed elements from the end of the list
            DataList.RemoveRange(DataList.Count - coreIndices.Length, coreIndices.Length);

            return DataList;
        }

        // Adapted from Stack Overflow answer 63496225 revision 4
        // https://stackoverflow.com/revisions/63496225/4
        [Benchmark()]
        public List<int> Answer63496225_TheodorZoulias()
        {
            HashSet<int> indicesSet = new HashSet<int>(RemovalList);
            int index = 0;

            DataList.RemoveAll(_ => indicesSet.Contains(index++));

            return DataList;
        }


        // Adapted from Stack Overflow answer 63496768 revision 2
        // https://stackoverflow.com/revisions/63496768/2
        [Benchmark()]
        public List<int> Answer63496768_CoolBots()
        {
            List<int> sortedIndicies = RemovalList.Distinct().OrderBy(i => i).ToList();

            int sourceStartIndex = 0;
            int destStartIndex = 0;
            int spanLength = 0;

            int skipCount = 0;

            // Copy items up to last index to be skipped
            foreach (int skipIndex in sortedIndicies)
            {
                spanLength = skipIndex - sourceStartIndex;
                destStartIndex = sourceStartIndex - skipCount;

                for (int i = sourceStartIndex; i < sourceStartIndex + spanLength; i++)
                {
                    DataList[destStartIndex] = DataList[i];
                    destStartIndex++;
                }

                sourceStartIndex = skipIndex + 1;
                skipCount++;
            }

            // Copy remaining items (between last index to be skipped and end of list)
            spanLength = DataList.Count - sourceStartIndex;
            destStartIndex = sourceStartIndex - skipCount;

            for (int i = sourceStartIndex; i < sourceStartIndex + spanLength; i++)
            {
                DataList[destStartIndex] = DataList[i];
                destStartIndex++;
            }

            DataList.RemoveRange(destStartIndex, sortedIndicies.Count);

            return DataList;
        }

        // Adapted from Stack Overflow answer 63495657 revision 6
        // https://stackoverflow.com/revisions/63495657/6
        [Benchmark()]
        public List<int> Answer63495657_NetMage()
        {
            List<int> removeAtList = RemovalList.Distinct().OrderBy(i => i).ToList();

            int srcCount = DataList.Count;
            int ralCount = removeAtList.Count;
            int removeAtIndice = 1;

Net*_*age 17

由于源列表的顺序很重要，您可以将每个项目向下移动列表，跳过要删除的索引，然后删除列表的末尾。

更新：采用 .Net Core 源代码RemoveAll并将其修改为索引列表而不是谓词。

更新 2：优化为尽可能不重复测试。

更新 3：简化为具有额外代码的优化在基准测试中被证明较慢。

拥有src作为大名单，并removeAtList为指数在一些随机的顺序删除，你可以这样做：

removeAtList.Sort();

var srcCount = src.Count;
var ralCount = removeAtList.Count;
var removeAtIndice = 1;
var freeIndex = removeAtList[0];
var current = freeIndex+1;
while (current < srcCount) {
    while (removeAtIndice < ralCount && current == removeAtList[removeAtIndice]) {
        ++current;
        ++removeAtIndice;
    }

    if (current < srcCount)
        src[freeIndex++] = src[current++];
}

src.RemoveRange(freeIndex, srcCount-freeIndex);
Run Code Online (Sandbox Code Playgroud)

对于 10 亿个随机整数元素列表和 1000 - 3000 个随机索引元素列表，使用此算法每次删除我得到 1.1 毫秒。使用RemoveAt，我每次删除超过 232.77 毫秒，所以这大约快 200 倍。

Mar*_*ell 6

允许并行化的一种方法是将列表分成多个片段；也许最初（任意）分开 100 万个元素的平板。只要每个slab保持自己的计数，就可以通过索引将工作拆分为不同slab的移除（纯粹基于计数），然后同时进行实际的移除工作。如果您在每个空间中留出一些备用容量，您还可以更便宜地将元素添加到中间，因为您通常只接触一块平板。随机访问会慢一点，因为你可能需要查看多个slab计数来确定正确的slab，但是如果slab计数保持在一个连续的向量中（而不是针对每个slab），你应​​该有很好的内存缓存命中在做的时候。

Coo*_*ots 6

这个答案基于这里的其他答案 - 主要是，我正在列表中向上移动元素，正如@Vernou（在他们的答案中）和@BACON（在评论中）所建议的那样。这个最终是高性能的（与我的前几种方法不同），并且比迄今为止发布的其他解决方案更快，至少在我的测试中 - 我尝试了 OP 的2_000_000_000条目和2_000索引设置- 在我的笔记本电脑上运行时间不到 10 秒（i7-8550U @ 1.8GHz，16GB 内存）：

static void FilterOutIndicies(List<int> values, List<int> sortedIndicies)
{
    int sourceStartIndex = 0;
    int destStartIndex = 0;
    int spanLength = 0;

    int skipCount = 0;

    // Copy items up to last index to be skipped
    foreach (var skipIndex in sortedIndicies)
    {
        spanLength = skipIndex - sourceStartIndex;
        destStartIndex = sourceStartIndex - skipCount;

        for (int i = sourceStartIndex; i < sourceStartIndex + spanLength; i++)
        {
            values[destStartIndex] = values[i];
            destStartIndex++;
        }

        sourceStartIndex = skipIndex + 1;
        skipCount++;
    }

    // Copy remaining items (between last index to be skipped and end of list)
    spanLength = values.Count - sourceStartIndex;
    destStartIndex = sourceStartIndex - skipCount;

    for (int i = sourceStartIndex; i < sourceStartIndex + spanLength; i++)
    {
        values[destStartIndex] = values[i];
        destStartIndex++;
    }

    values.RemoveRange(destStartIndex, sortedIndicies.Count);
}
Run Code Online (Sandbox Code Playgroud)

归档时间：

查看次数：

1482 次

最近记录：

4 年，7 月 前
如何在C#中实现Array.Copy？ 12
删除给定索引处的列表元素 10
更多相关链接
相关归档
C#中的Java Map等价物 146
在VB.NET中标记类静态 82
将JSON数组转换为Python列表 60
如何使用AspNet.Identity使用Asp.Net MVC5 RTM位登录/验证用户？ 47
使用foreach同时迭代多个列表(语法糖) 33
clock_gettime()是否适合亚微秒时序？ 20
CPU缓存关键步幅测试根据访问类型给出意外结果 13
从malloc()进行的Windows和Linux本机OS /系统调用是什么？ 8
JS in Chrome(V8)的性能问题 7
查找数组中 Span&lt;T&gt; 的位置 6
难疑归档
应该在JavaScript比较中使用哪个等于运算符(== vs ===)？ 5666
了解切片表示法 3024
使用JavaScript获取当前网址？ 2882
循环内的JavaScript闭包 - 简单实用的例子 2689
是否有标准函数来检查JavaScript中的null,undefined或blank变量？ 2088
如何生成随机字母数字字符串？ 1679
什么是非捕获组？(？:)做什么？ 1653
查看未发布的Git提交 1649
命令折叠代码的所有部分？ 1576
如何将NodeJS和NPM更新到下一个版本？ 1573