为什么l.insert(0,i)比python中的l.append(i)慢？

Question

我测试了两种不同的方法来反转python中的列表.

import timeit

value = [i for i in range(100)]
def rev1():
    v = []
    for i in value:
        v.append(i)
    v.reverse()

def rev2():
    v = []
    for i in value:
        v.insert(0, i)

print timeit.timeit(rev1)
print timeit.timeit(rev2)

有趣的是,将值插入第一个元素的第二个方法比第一个元素慢得多.

20.4851300716
73.5116429329

为什么是这样？在操作方面,将元件插入头部似乎并不昂贵.

Answer 1

insert是一种O(n)操作,因为它要求插入位置处或之后的所有元素向上移动一个.append另一方面,通常是O(1)(并且O(n)在最坏的情况下,必须分配更多空间时).这解释了实质性的时差.

这里详细记录了这些方法的时间复杂性.

我引用:

在内部,列表表示为数组; 最大的成本来自于超出当前分配大小(因为一切都必须移动),或者在开头附近的某处插入或删除(因为之后的所有内容都必须移动).

现在,回到你的代码,我们可以看到这rev1()是一个O(n)实现,而rev2()事实上,所以它会慢得多.O(n2)rev2()