此列表代码的追加和连接的复杂性差异？

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)。

最起码，不要使用+连接；使用 += augmented 串联，这与 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]

此列表代码的追加和连接的复杂性差异？

Difference in complexity of append and concatenate for this list code?

python

big-o

time-complexity

python-2.7