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

发布时间：2020-12-12 06:47:53 所属栏目：MsSql教程来源：网络整理

导读：我测试了两种不同的方法来反转 python中的列表. import timeitvalue = [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(

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

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

解决方法

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

这些方法的时间复杂性已完整记录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()会慢很多.

（编辑：李大同）

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