我正在寻找一种快速从 C# 的 List<T> 中删除项目的方法。文档中指出，List.Remove() 和 List.RemoveAt() 操作都是 O(n)。
这严重影响了我的应用程序。
我编写了几种不同的删除方法，并将它们全部测试在一个包含 500,000 个项目的 List<String> 上。以下是测试用例...
概览
我编写了一个方法，它生成一个字符串列表，其中每个数字都以字符串形式表示（"1"、"2"、"3"，等等）。然后我尝试着从列表中删除每五个项目。以下是用于生成列表的方法：
private List<String> GetList(int size)
{
List<String> myList = new List<String>();
for (int i = 0; i < size; i++)
myList.Add(i.ToString());
return myList;
}
测试1：RemoveAt()
这是我用来测试RemoveAt()方法的测试。
private void RemoveTest1(ref List<String> list)
{
for (int i = 0; i < list.Count; i++)
if (i % 5 == 0)
list.RemoveAt(i);
}
测试2：Remove()
这是我用来测试Remove()方法的测试。
private void RemoveTest2(ref List<String> list)
{
List<int> itemsToRemove = new List<int>();
for (int i = 0; i < list.Count; i++)
if (i % 5 == 0)
list.Remove(list[i]);
}
测试3：将其设置为null，排序，然后删除范围
在这个测试中，我循环遍历了列表一次，并将要删除的项设置为null。然后，我对列表进行了排序（以便null位于顶部），并删除了所有设置为null的顶部项。
注意：这重新排序了我的列表，因此我可能需要将其放回正确的顺序。
private void RemoveTest3(ref List<String> list)
{
int numToRemove = 0;
for (int i = 0; i < list.Count; i++)
{
if (i % 5 == 0)
{
list[i] = null;
numToRemove++;
}
}
list.Sort();
list.RemoveRange(0, numToRemove);
// Now they're out of order...
}
测试4：创建一个新列表，并将所有“好”的值添加到新列表中
在这个测试中，我创建了一个新的列表，并将所有保留项添加到了新的列表中。然后，我将所有这些项目放入了原始列表中。
private void RemoveTest4(ref List<String> list)
{
List<String> newList = new List<String>();
for (int i = 0; i < list.Count; i++)
{
if (i % 5 == 0)
continue;
else
newList.Add(list[i]);
}
list.RemoveRange(0, list.Count);
list.AddRange(newList);
}
测试5：将其设为 null，然后使用FindAll()
在此测试中，我将所有要删除的项目设置为null，然后使用FindAll()功能查找所有不是null的项目。
private void RemoveTest5(ref List<String> list)
{
for (int i = 0; i < list.Count; i++)
if (i % 5 == 0)
list[i] = null;
list = list.FindAll(x => x != null);
}
测试6：将其设置为null，然后使用RemoveAll()方法
在此测试中，我将所有要删除的项设置为null，然后使用RemoveAll()方法删除所有不为null的项。
private void RemoveTest6(ref List<String> list)
{
for (int i = 0; i < list.Count; i++)
if (i % 5 == 0)
list[i] = null;
list.RemoveAll(x => x == null);
}
int numItems = 500000;
Stopwatch watch = new Stopwatch();
// List 1...
watch.Start();
List<String> list1 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
watch.Reset(); watch.Start();
RemoveTest1(ref list1);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();
// List 2...
watch.Start();
List<String> list2 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
watch.Reset(); watch.Start();
RemoveTest2(ref list2);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();
// List 3...
watch.Reset(); watch.Start();
List<String> list3 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
watch.Reset(); watch.Start();
RemoveTest3(ref list3);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();
// List 4...
watch.Reset(); watch.Start();
List<String> list4 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
watch.Reset(); watch.Start();
RemoveTest4(ref list4);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();
// List 5...
watch.Reset(); watch.Start();
List<String> list5 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
watch.Reset(); watch.Start();
RemoveTest5(ref list5);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();
// List 6...
watch.Reset(); watch.Start();
List<String> list6 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
watch.Reset(); watch.Start();
RemoveTest6(ref list6);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();
结果
00:00:00.1433089 // Create list
00:00:32.8031420 // RemoveAt()
00:00:32.9612512 // Forgot to reset stopwatch :(
00:04:40.3633045 // Remove()
00:00:00.2405003 // Create list
00:00:01.1054731 // Null, Sort(), RemoveRange()
00:00:00.1796988 // Create list
00:00:00.0166984 // Add good values to new list
00:00:00.2115022 // Create list
00:00:00.0194616 // FindAll()
00:00:00.3064646 // Create list
00:00:00.0167236 // RemoveAll()
笔记和评论
前两个测试实际上并没有从列表中删除每个第五个项，因为在每次删除后都重新排序了列表。事实上，在 500,000 项中，只有 83,334 项被删除了（应该是 100,000 项）。我对此无可厚非 - 显然，Remove()/RemoveAt() 方法并不是一个好主意。
尽管我试图从列表中删除第五个项目，但在 现实中 不会存在这样的模式。要删除的条目将是随机的。
虽然我在这个例子中使用了一个
List<String>，但情况并不总是如此。它可以是一个List<Anything>从一开始就不把项目放入列表不是一个选项。
其他方法（3-6）在比较中表现得更好，但我有点担心——在 3、5 和 6 中，我被迫将一个值设置为
null，然后根据这个标记删除所有项。我不喜欢这种方法，因为我可以想象到一种情况，在列表中的某个项目可能是null，而它会被意外地删除。
我的问题是：快速从List<T>中删除多个项目的最佳方法是什么？我尝试过的大多数方法看起来非常丑陋，潜在危险。是List数据结构不正确吗？
现在，我倾向于创建一个新的列表，并将好的项添加到新的列表中，但似乎应该有更好的方法。
List<T>？除非你需要随机访问，否则LinkedList<T>可能更为合适。 - Jon Skeet