python插入VS追加

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

请注意，您的结果将取决于精确的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，但我们必须移动所有其他值（甚至不能复制，这可能会减少内存的开销）。