Python串接vs列表追加速度

Question

摘自interactivepython.org:

def test1():  # concat
    l = []
    for i in range(1000):
        l = l + [i]
def test2():  # append
    l = []
    for i in range(1000):
        l.append(i)

---

concat  6.54352807999 milliseconds
append  0.306292057037 milliseconds

其中底部块是运行时。

它说连接是O(k)，其中k是"被连接的列表的长度"。我不确定这是指你正在添加的列表(原始)，还是你将要添加的列表。但在这两个循环中，似乎每次迭代只执行一步。为什么append这么快?

Answer 1

如果将test1更改为:

def test1():  # concat
    l = []
    for i in range(1000):
        l += [i] 

时间会更接近，你实际上是在做append所做的事情，而不是每次都创建一个新的列表。

In [26]: %timeit test1()
10000 loops, best of 3: 169 µs per loop
In [27]: %timeit test2()
10000 loops, best of 3: 115 µs per loop

如果你把print id放在你的代码中，你会看到在test1中你每次都创建一个新对象，但在test2中它总是相同的列表:

In [41]: test1()
139758194625352
139758206001808
139758205966960
139758194625352
139758206001808
139758205966960
139758194625352
139758206001808
139758205966960
139758194625352
Out[41]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In [42]: test2()
139758206002600
139758206002600
139758206002600
139758206002600
139758206002600
139758206002600
139758206002600
139758206002600
139758206002600
139758206002600
Out[42]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Answer 2

因为每次迭代必须构建一个新的 list对象:

每次创建一个新列表比在现有列表中添加一个项要昂贵得多。

在底层，.append()将填充C数组中预分配的索引，并且列表对象只需要周期性地增长该数组。另一方面，构建一个新的列表对象必须每次都分配一个C数组。