Python连接与列表上的附加速度

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是"连接列表的长度".我不确定这是否意味着您要添加的列表(原始),或者您要添加的列表.但在这两个循环中,您似乎只是每次迭代执行一步.那么为什么追加这么快呢？

Answer 1

因为串联必须在每次迭代中构建一个新的列表对象：

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

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

Answer 2

如果将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]