c# - List.Insert 是否有任何性能损失？

Question

给定一个列表：

List<object> SomeList = new List<object>();

做：

SomeList.Insert(i, val);

比。

SomeList.Add(val);

有任何性能损失吗？如果是，它如何依赖于：
- i- 插入索引
- SomeList.Count- 列表的大小

Answer 1

List 类是 ArrayList 类的通用等价物。它使用一个数组来实现 IList 泛型接口，该数组的大小根据需要动态增加。

（来源）

这意味着内部数据存储为一个数组，因此执行insert它可能需要将所有元素移动以腾出空间，因此它的复杂性是 O(N)，add而是一个（摊销的）常数时间O(1) 操作，所以是的。

摘要 - 是的，它几乎总是会变慢，而且你的列表越大，它就会越慢。

Answer 2

如有疑问，请进行经验实验：

List<object> SomeList = new List<object>();

Stopwatch sw = new Stopwatch();
sw.Start();
for (var i = 0; i < 100000; i++)
    SomeList.Insert(0, String.Empty);
sw.Stop();
Console.WriteLine(sw.Elapsed.TotalMilliseconds);
sw.Reset();

SomeList = new List<object>();
sw.Start();
for (var i = 0; i < 100000; i++)
    SomeList.Add(String.Empty);
sw.Stop();
Console.WriteLine(sw.Elapsed.TotalMilliseconds);

在我的Insert机器上需要 2800 毫秒；需要Add0.8ms。所以是的，Insert性能要差得多。

Answer 3

我意识到这已经得到了彻底的回答，但我想指出，这些信息在 MSDN 文档中很容易获得。

状态的文档List<T>.Insert()：

此方法是一个 O(n) 操作，其中 n 是 Count。

状态的文档List<T>.Add()：

如果 Count 小于 Capacity，则此方法是 O(1) 操作。如果需要增加容量以容纳新元素，则此方法变为 O(n) 操作，其中 n 为 Count。

如果您碰巧问了这个问题，因为您想频繁地添加到列表的前面和后面，那么要使用的适当数据结构是Deque.

Stephen Cleary在这里提供了一个很好的 Deque 实现：http: //nitodeque.codeplex.com/

Answer 4

我的第一个想法是“是的，存在性能损失，因为Insert需要将列表中的所有项目移动到一个插槽以便为新项目腾出空间”——但后来我更仔细地阅读了这个问题。所以：

一般来说，Insert需要（可能很多）更多时间，因为它需要移动列表中已经存在的所有项目以为新项目腾出空间，所以这是对列表长度的 O(n) 操作（如果列表是满容量它还需要调整大小，但这仍然是一个 O(n) 操作）。另一方面，Add只需附加新项目而不需要移动任何东西，因此它更快 - 一个 O(1) 操作（除非列表需要调整大小，如上所述）。

在这个特定的例子中，列表一开始是空的，不会有性能差异。

当然，所有这些都没有实际意义，因为除非您有记录在案的性能问题，否则您应该根据您的意图选择方法。

Answer 5

对于一个空列表，它没有什么不同。

但是对于其他任何事情，它必须更慢*，因为要在前面插入，整个后备数组需要向右移动一个。

*除了Add导致Capacity增加的地方。

Answer 6

当然可以。

由于List<T>由数组支持，因此要在列表开头插入的任何操作都必须移动（或复制）数组的所有其他元素。添加到列表末尾的操作将在恒定时间内发生，而与列表中的项目数无关。

Answer 7

我建立在 Pattermiester 的性能测试之上。当我想到插入时，我想到了一个数组，为了添加到一个数组中，您必须指定要插入的索引。执行 Add(0, object) 似乎违反直觉。此外，当您进行性能测试时，总是首先创建一个扔掉的运行。有时它需要的时间比实际应该的要长。

结果

2.282 - Throw Away Run
2.6847 - List Insert By Index without Capacity
10544.9766 - List Insert At Index 0 without Capacity
1.8426 - List Add without Capacity
2.0835 - List Insert By Index with Capacity
1.4952 - List Add with Capacity
9323.699 - List Insert at Index 0 with Capacity

代码

        var size = 200000;
        //First test sometimes has a bad count
        List<object> SomeList = new List<object>();
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (var i = 0; i < size; i++)
            SomeList.Insert(i, String.Empty);
        sw.Stop();
        Console.WriteLine(sw.Elapsed.TotalMilliseconds + " - Throw Away Run");
        sw.Reset();

        SomeList = new List<object>();
        sw = new Stopwatch();
        sw.Start();
        for (var i = 0; i < size ; i++)
            SomeList.Insert(i, String.Empty);
        sw.Stop();
        Console.WriteLine(sw.Elapsed.TotalMilliseconds+" - List Insert By Index without Capacity");
        sw.Reset();

        SomeList = new List<object>();
        sw = new Stopwatch();
        sw.Start();
        for (var i = 0; i < size; i++)
            SomeList.Insert(0, String.Empty);
        sw.Stop();
        Console.WriteLine(sw.Elapsed.TotalMilliseconds + " - List Insert At Index 0 without Capacity");
        sw.Reset();

        SomeList = new List<object>();
        sw.Start();
        for (var i = 0; i < size; i++)
            SomeList.Add(String.Empty);
        sw.Stop();
        Console.WriteLine(sw.Elapsed.TotalMilliseconds+" - List Add without Capacity");
        sw.Reset();

        SomeList = new List<object>(size);
        sw = new Stopwatch();
        sw.Start();
        for (var i = 0; i < size; i++)
            SomeList.Insert(i, String.Empty);
        sw.Stop();
        Console.WriteLine(sw.Elapsed.TotalMilliseconds+" - List Insert By Index with Capacity");
        sw.Reset();

        SomeList = new List<object>(size);
        sw.Start();
        for (var i = 0; i < size; i++)
            SomeList.Add(String.Empty);
        sw.Stop();
        Console.WriteLine(sw.Elapsed.TotalMilliseconds+" - List Add with Capacity");
        sw.Reset();

        SomeList = new List<object>(size);
        sw = new Stopwatch();
        sw.Start();
        for (var i = 0; i < size; i++)
            SomeList.Insert(0, String.Empty);
        sw.Stop();
        Console.WriteLine(sw.Elapsed.TotalMilliseconds + " - List Insert at Index 0 with Capacity");

所以看起来 Add 比 insert 性能要好一些。但是，如果您使用的是 Insert(0, "")，那么您肯定会扼杀性能。如果你想要最好的性能，而不是使用容量。