python insert vs append

Question

我已经编写了基本的python片段,首先在列表中插入值然后反转它们.我发现insert和append方法之间的执行速度差异很大.

小片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的性能比snippet1好得多,因为我之前通过插入数字直接执行反向操作.但是,所用的时间不然.我无法理解为什么后一种方法需要更多时间来执行,即使该方法看起来更优雅.有没有人对此有任何解释？

Answer 1

下面是完整的答案,从邓肯展位:

列表由指向其包含的对象的指针数组实现.

每次调用'insert(0,indx)'时,列表中已有的所有指针都必须向上移动一次,然后才能在开头插入新指针.

当您调用'append(indx)'时,如果当前为新元素分配的块中没有足够的空间,则只需复制指针.如果有空间则无需复制现有元素,只需将新元素放在最后并更新长度字段即可.每当必须分配新块时,特定追加将不会比插入更快,但是如果您希望进一步扩展列表,则将分配一些额外空间.

如果你希望insert更快,也许你认为Python使用了链表实现.它没有这样做,因为在实践中(对于大多数应用程序),基于列表的实现提供了更好的性能.

其实我没有别的东西可以补充.

Answer 2

请注意,您的结果将取决于精确的Python实现.cpython(和pypy)会自动调整列表大小并过度配置空间以供将来添加,从而加快速度append.

在内部,列表只是具有恒定大小的内存块(在堆上).有时你很幸运,可以增加块的大小,但在很多情况下,一个对象已经存在.例如,假设您为列表分配了大小为4的块[a,b,c,d],而另一段代码为字典分配了大小为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,但我们不得不移动(甚至不是复制,这在内存中可能更便宜)所有其他值.

Answer 3

如果您需要一个在开始时插入的数据结构与附加一样有效,那么您应该考虑使用双端队列.