我测试了两种不同的方法来反转
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)).这解释了实质性的时差.
我引用：
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()会慢很多.
