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

我测试了两种不同的方法来反转 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

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

解决方法

这些方法的时间复杂性已完整记录here.

我引用：

Internally,a list is represented as an array; the largest costs come from growing beyond the current allocation size (because everything must move),or from inserting or deleting somewhere near the beginning (because everything after that must move).

现在,回到你的代码,我们可以看到rev1()是一个O(n)实现,而rev2()实际上是O(n2),所以有意义的是rev2()会慢很多.

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!