python 插入与追加

Question

我写了一些简单的Python代码，首先是把值放进一个列表，然后再把它们反转。我发现使用插入和追加这两种方法的执行速度差别很大。

代码片段 1:

L = []
for i in range(10**5):
 L.append(i)
L.reverse()

执行这个的时间：

real    0m0.070s
user    0m0.064s
sys         0m0.008s

代码片段 2:

l = []
for i in range(10**5):
 l.insert(0,i)

执行这个的时间：

real    0m5.645s
user    0m5.516s
sys         0m0.020s

我原本以为代码片段 2 的表现会比代码片段 1 好很多，因为我是在插入数字的时候直接进行反转操作。但实际的执行时间却显示并非如此。我搞不懂为什么后面的方法执行起来反而更慢，尽管这个方法看起来更优雅。有没有人能解释一下这个情况？

Answer 1

如果你需要一种数据结构，它在开头插入和在末尾添加数据时都很高效，那么你可以考虑使用deque。

Answer 2

以下是来自 Duncan Booth 的完整回答：

列表是通过一个指针数组来实现的，这些指针指向它包含的对象。

每当你调用 'insert(0, indx)' 时，列表中已经存在的所有指针都必须向上移动一个位置，才能在最前面插入新的指针。

而当你调用 'append(indx)' 时，指针只有在当前分配的空间不够放下新元素时才需要被复制。如果有足够的空间，就只需把新元素放到最后，并更新列表的长度。每当需要分配新的空间时，这个 'append' 操作的速度不会比 'insert' 快，但会额外分配一些空间，以防你想继续扩展列表。

如果你认为 'insert' 会更快，可能是因为你以为 Python 使用的是链表实现。实际上并不是这样，因为在大多数应用中，基于列表的实现性能更好。

我实际上没有其他要补充的内容。

Answer 3

请注意，你的结果会受到具体的Python实现方式的影响。像cpython和pypy这样的实现会自动调整你的列表大小，并且会提前分配一些额外的空间，以便将来添加新元素时更快。

从内部来看，列表其实就是一块固定大小的内存区域（在堆上）。有时候你运气好，可以直接增大这块内存的大小，但很多时候，那里已经有其他东西了。比如，假设你为一个列表 [a,b,c,d] 分配了4个单位的内存，而另一段代码为一个字典分配了6个单位的内存：

Memory  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
       |a b c d| | dictionary |

假设你的列表现在有4个元素，如果再添加一个元素，你可以简单地把列表的大小调整到5：

Memory  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
       |a b c d e| dictionary |

但是，如果你现在还需要再添加一个元素，该怎么办呢？

其实你只能申请新的空间，并把列表里的内容复制过去。

Memory 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
                | dictionary |a  b  c  d  e  f |

值得注意的是，如果你提前申请了更多的空间（就是前面提到的“超额配置”），那么你就只需要偶尔调整（并可能复制）列表的大小。

相反，当你在位置0插入元素时，你总是需要复制整个列表。比如我们要插入 x：

Memory  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
orig   |a b c d| |dictionary|
after  |x a b c d|dictionary|

虽然在末尾有足够的空间来添加x，但我们还是得把其他所有的值都移动（而不是简单复制，这样可能在内存上更省事）。