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

Question

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

• List.Remove
• List.RemoveAt

这严重影响了我的申请.

我写了几个不同的删除方法,并在List<String>500,000个项目上测试它们.测试用例如下所示......

---

概观

我写了一个方法,它会生成一个字符串列表,其中只包含每个数字的字符串表示形式("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()方法的测试.

private void RemoveTest1(ref List<String> list)
{
     for (int i = 0; i < list.Count; i++)
         if (i % 5 == 0)
             list.RemoveAt(i);
}

测试2:删除()

这是我用来测试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,排序,然后设置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();

结果

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项,但实际上不会有这样的模式.要删除的条目是随机的.

• 虽然我List<String>在这个例子中使用了a ,但情况并非总是如此.它可能是一个List<Anything>

• 不能将列表中的项目放在列表中不是一种选择.

• 其他方法(3 - 6)所有的表现要好得多,比较,不过我有点担心- 3,5,6我不得不设置一个值null,然后删除所有根据该定点的项目.我不喜欢这种方法,因为我可以设想一个场景,其中列表中的一个项目可能null会被无意中删除.

我的问题是:快速删除多个项目的最佳方法是什么List<T>？我尝试过的大部分方法看起来都很丑陋,对我来说也很危险.是一个List错误的数据结构？

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

Answer 1

在删除时,List不是一种有效的数据结构.您最好使用双链表(LinkedList),因为删除只需要在相邻条目中进行参考更新.

Answer 2

如果您很乐意创建新列表,则不必将设置项设置为null.例如:

// This overload of Where provides the index as well as the value. Unless
// you need the index, use the simpler overload which just provides the value.
List<string> newList = oldList.Where((value, index) => index % 5 != 0)
                              .ToList();

但是,您可能希望查看其他数据结构,例如LinkedList<T>或HashSet<T>.这实际上取决于您需要从数据结构中获得哪些功能.

Answer 3

我觉得HashSet,LinkedList或者Dictionary你会做得更好.

Answer 4

如果顺序无关紧要,那么就有一个简单的O(1)List.Remove方法.

public static class ListExt
{
    // O(1) 
    public static void RemoveBySwap<T>(this List<T> list, int index)
    {
        list[index] = list[list.Count - 1];
        list.RemoveAt(list.Count - 1);
    }

    // O(n)
    public static void RemoveBySwap<T>(this List<T> list, T item)
    {
        int index = list.IndexOf(item);
        RemoveBySwap(list, index);
    }

    // O(n)
    public static void RemoveBySwap<T>(this List<T> list, Predicate<T> predicate)
    {
        int index = list.FindIndex(predicate);
        RemoveBySwap(list, index);
    }
}

这个解决方案对内存遍历很友好,所以即使你需要先找到索引,它也会非常快.

笔记:

• 查找项目的索引必须为O(n),因为列表必须未排序.
• 链接列表在遍历时很慢,特别是对于具有较长寿命的大型集合.