用于列表的追加和连接复杂度的差异

Question

考虑以下用于形成一千个数字列表的方法。

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


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

print timeit.repeat(stmt=test1, number=100,repeat=2) 
print timeit.repeat(stmt=test2, number=100,repeat=2) 

输出：

[0.30474191033602543, 0.3783786557587963] 
[0.015134341605235302, 0.023081246200096328] 

为什么append方法比拼接好20倍左右。 AFAIK追加具有O（1）复杂性，而级联具有O（k）复杂性。虽然这里的K是1.

有没有我忽略的一些明显的东西？

Answer 1

您正在创建一个新的列表对象，每次通过连接。这需要将旧列表中的所有元素复制到新列表中，再加上一个。所以是的，使用l = l + [i]是O（N）算法，而不是O（1）。

至少，不要使用+级联;使用+=增强串联，这是同样的事情list.extend()与重新分配到同一个参考：

def test3(): 
    l = [] 
    for i in range(1000): 
     l += [i] # or use l.extend([i]) 
    return l 

这将产生：

>>> print timeit.repeat(stmt=test1, number=100, repeat=2) 
[0.1333179473876953, 0.12804388999938965] 
>>> print timeit.repeat(stmt=test2, number=100, repeat=2) 
[0.01052403450012207, 0.007989168167114258] 
>>> print timeit.repeat(stmt=test3, number=100, repeat=2) 
[0.013209104537963867, 0.011193037033081055]