此列表代码的添加和连接复杂性是否不同?

问题描述

请考虑以下形成千个数字列表的方法.

Consider below methods for forming a list of thousand numbers.

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.

Why is the append method around 20 times better than concatenation. AFAIK append has O(1) complexity while concatenation has O(k) complexity. While K here is 1.

有什么明显的事情我被我忽略了吗?

Is there some obvious thing I overlooked?

推荐答案

您每次通过串联创建一个 new 列表对象.这需要将旧列表中的所有元素复制到一个新元素中，再加上一个额外元素.所以是的，使用l = l + [i]是O(N)算法，而不是O(1).

You are creating a new list object each time by concatenating. This requires copying all elements from the old list into a new one, plus one extra. So yes, using l = l + [i] is an O(N) algorithm, not O(1).

至少不要使用+串联；使用+= 增强的串联，这与list.extend()相同，只是重新分配了相同的引用:

At the very least, don't use + concatenation; use += augmented concatenation, which is the same thing as list.extend() with a re-assignment to the same reference:

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]

这篇关于此列表代码的添加和连接复杂性是否不同?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！