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

这里是完整的 answer来自邓肯布斯:

A list is implemented by an array of pointers to the objects it contains.

Every time you call 'insert(0, indx)', all of the pointers already in the list have to be moved up once position before the new one can be inserted at the beginning.

When you call 'append(indx)' the pointers only have to be copied if there isn't enough space in the currently allocated block for the new element. If there is space then there is no need to copy the existing elements, just put the new element on the end and update the length field. Whenever a new block does have to be allocated that particular append will be no faster than an insert, but some extra space will be allocated just in case you do wish to extend the list further.

If you expected insert to be faster, perhaps you thought that Python used a linked-list implementation. It doesn't do this, because in practice (for most applications) a list based implementation gives better performance.

其实我没有什么要补充的。