这个列表代码的附加和连接的复杂性有何不同？

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]

为什么追加方法比连接好大约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]