从List中删除单个项目的最快方法是什么 没有重复的订单重要吗？

Question

我有一个没有重复的项目列表，其中订单很重要。

我需要定期从此列表中删除一个项目。

一个实际的例子是列表绑定的UI控件，例如允许删除的DataGridView。

用户希望以特定顺序查看项目，因此删除后剩余项目应保留其订购。

下面是一些示例代码，似乎表明列表项删除是O(n)因为

（1）必须迭代列表以通过匹配标准找到要删除的项目

（2）List.RemoveAt方法必须洗掉剩下的物品

public class Item
{
  public string Name {get; set;}
  public string Description {get; set;}
}

public List<Item> Items = new List<Item>();

public void AddItem(string name, string description)
{
  Items.Add(new Item {Name=name, Description=description});
}

public void RemoveItem(string name)
{
  for (int i=0; i<Items.Count; i++)
  {
    if (Items[i].Name == name)
    {
      Items.RemoveAt(i);
      break;
    }
  }
}

有没有更快的方法？

LinkedList<T>将无法正常工作，因为它无法为滚动和分页编制索引。此外，对于高项目计数，由于缓存未命中，LinkedList<T>项目删除实际上较慢。

Answer 1

RemoveAt需要O（n）时间。因为它必须将项目向左移动，从索引i开始到n（Items.Count）。类似于IndexOf。

这是你的代码的渐近估计：

public void RemoveItem(string name)
{
  foreach (var item in Items) //n times
  {
    if (item.Name == name)
    {
      Items.RemoveAt(Items.IndexOf(position)); // O(n) + O(n) => O(n)
    }
  }

  // => O(n * n)
}

它在O（n ^ 2）时间内运行。

这段代码怎么样？

for (int i = Items.Count - 1; i >= 0; i--) // n times
{
    if (Items[i].Name == name)
    {
        Items.RemoveAt(i); //O(n)
    }
}

所以这也在O（n ^ 2）中运行

但是这段代码：

Items.RemoveAll(i => item.Name == name);

在O（n）时间运行。您应该看到此方法的实现以进行证明。 RemoveAll通过列表中的项目迭代ONCE，如果满足条件，它将在迭代时开始移位。每个步骤中的这种移位是单个分配，即O（1）。因此整个方法在O（n）时间内运行，这比你的实现要快得多。

更新：问题现在包含删除行后的break;。

在该代码中，查找项目将在找到并且将开始移除后停止，这将花费O（n）+ O（n）=> O（n）。

因此，有问题的代码和RemoveAll之间不会有任何渐近的差异。

所以它不是更快，也不是，但仍然RemoveAll是一个更清洁的代码恕我直言。

Answer 2

您不需要循环也不需要自定义方法。试试这个：

Items.RemoveAll(i => item.Name == name);

编辑 正如@Gian Paolo评论的那样，对于List数据结构，在最好的情况下，它具有O（n）的复杂性。如果您想获得更好的性能，可以考虑检查其他数据结构，包括LinkedList，Dictionary或HashSet。

Answer 3

一种方法是在项目上使用传统循环，如果名称匹配则删除，

for (int i = Items.Count - 1; i >= 0; i--)
{
    if (Items[i].Name == name)
    {
        Items.RemoveAt(i);
        break;
    }
}