Python的列表append方法为何如此快速？

Question

我正在比较Python中向列表添加条目的不同方法。我在我的计算机上进行了测试，结果当然会因其他电脑而异。

选项1：仅使用50,000个条目需要5.80秒！

a = []
for i in range(50000):
    a = a + [i]

选项2: 10,000,000个项目，需要2.27秒

a = []
for i in range(10000000):
    a += [i]

选项3：1.53秒10,000,000个项目。

a = []
for i in range(10000000):
    a.append(i)

毫不意外，选项1很慢，因为它每次都创建一个新的列表副本。

选项2使用增强赋值运算符，修改原始列表，速度快得多。

但是，选项3仍然显著更快。我认为使用append()方法和增强赋值运算符会产生相同的结果。

为什么append()方法仍然比+=运算符快那么多？

PS： 我的Python版本：

Python 3.5.2（v3.5.2：4def2a2901a5，Jun 25 2016，22:18:55）[MSC v.1900 64 bit(AMD64)] on win32

根据taskinoor的答案，额外的开销是由于在每个循环迭代中创建一个新的列表对象[i]。这对我来说似乎是合理的。我创建了新的测试代码，试图避免在每次迭代中创建新对象。是的，现在它更快了，但仍然不像使用append()那样快，因为现在我又有了额外分配的开销。但我认为这证明了taskinoor的观点。

选项4: 1000万项需要1.91秒 （选项2的改进版）

a = []
b = [0]
for i in range(10000000):
    b[0] = i
    a += b

- David

---

我猜它们在增长基础列表时分配额外空间的数量不同。 - Filip Haglund

您正在创建一个新列表并进行扩展，而不是简单地添加，所以添加操作更快也不足为奇。 - Padraic Cunningham

对于您的编辑，您正在执行setitem，然后再次扩展，因此并不令人惊讶。append只执行一个任务，并且执行得很好，实际上从来没有一个现实的用例需要使用任何其他方法将单个元素附加到列表中。 - Padraic Cunningham

Answer 1

第二种方法仍然需要创建临时列表[i]。看一下反汇编代码：

>>> import dis
>>> def func_2(a, i):
...     a += [i]
... 
>>> def func_3(a, i):
...     a.append(i)
... 
>>> dis.dis(func_2)
  2           0 LOAD_FAST                0 (a)
              3 LOAD_FAST                1 (i)
              6 BUILD_LIST               1
              9 INPLACE_ADD         
             10 STORE_FAST               0 (a)
             13 LOAD_CONST               0 (None)
             16 RETURN_VALUE        
>>> dis.dis(func_3)
  2           0 LOAD_FAST                0 (a)
              3 LOAD_ATTR                0 (append)
              6 LOAD_FAST                1 (i)
              9 CALL_FUNCTION            1
             12 POP_TOP             
             13 LOAD_CONST               0 (None)
             16 RETURN_VALUE        
>>> 

第二种方法需要6 BUILD_LIST，但第三种方法不需要。可能还有其他原因，但这应该是第三种方法更快的主要原因。

- taskinoor

---

我理解这个。是在 += 操作符后面的 [i] 导致了创建新列表对象的开销。 - David