如何快速从列表中删除项目

我正在寻找一种快速从 C# 中删除项目的方法List<T>。该文档指出List.Remove() and List.RemoveAt()操作都是O(n)

• 列表.删除 http://msdn.microsoft.com/en-us/library/cd666k3e.aspx
• 列表.RemoveAt http://msdn.microsoft.com/en-us/library/5cw9x18z%28v=vs.80%29.aspx

这严重影响了我的申请。

我编写了一些不同的删除方法并在List<String>拥有 500,000 件商品。测试用例如下所示...

Overview

我编写了一个方法，该方法会生成一个字符串列表，其中仅包含每个数字（“1”、“2”、“3”等）的字符串表示形式。然后我尝试remove列表中的每第 5 项。这是用于生成列表的方法：

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() method.

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() method.

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，排序，然后RemoveRange

在这个测试中，我循环遍历列表一次并将要删除的项目设置为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();

Results

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()

注释和评论

• 前两个测试实际上并没有从列表中删除每第 5 个项目，因为每次删除后都会对列表进行重新排序。事实上，在 500,000 个项目中，只有 83,334 个被删除（应该是 100,000 个）。我对此表示同意 - 显然，Remove()/RemoveAt() 方法无论如何都不是一个好主意。

• 虽然我试图从列表中删除第 5 项，但在reality不会有这样的模式。要删除的条目将是随机的。

• 虽然我用了一个List<String>在本例中，情况并非总是如此。它可能是一个List<Anything>

• 一开始就不将项目放入列表中是not一个选项。

• 其他方法 (3 - 6) 都表现得更好，比较，但是我有点担心——在 3、5 和 6 中，我被迫将一个值设置为null，然后根据这个哨兵删除所有项目。我不喜欢这种方法，因为我可以想象一个场景，其中列表中的一项可能是null并且它会被无意中删除。

我的问题是：从文件中快速删除许多项目的最佳方法是什么？List<T>？对我来说，我尝试过的大多数方法看起来都很丑陋，而且有潜在的危险。是一个List错误的数据结构？

现在，我倾向于创建一个新列表并将好的项目添加到新列表中，但似乎应该有更好的方法。

在删除方面，列表并不是一种有效的数据结构。您最好使用双链表 (LinkedList)，因为删除只需要相邻条目中的引用更新。