为什么在Python中，l.insert(0, i)比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

为什么呢？就操作而言，在头部插入元素似乎并不那么耗费。

- prosseek

---

如果您需要类似于链表的数据结构，请使用deque：http://docs.python.org/2/library/collections.html#collections.deque - Rusty Rob

Answer 1

insert是一个O(n)的操作，因为它需要将插入位置及其后面的所有元素向上移动一个位置。另一方面，append通常是O(1)的（在最坏情况下，即需要分配更多空间时，可能是O(n)）。这解释了两者之间的显着时间差异。

这些方法的时间复杂度已经在这里得到了全面记录。

我引用:

在内部，列表被表示为一个数组；最大的代价来自于超过当前分配大小（因为必须移动所有内容）或者从靠近开头的地方进行插入或删除（因为之后的所有内容都必须移动）。

现在回到您的代码，我们可以看到rev1()是一个O(n)的实现，而rev2()实际上是O(n2)，所以rev2()会慢得多是有道理的。

- arshajii

Answer 2

在Python中，列表被实现为数组。如果你向数组追加一个元素，数组的保留空间将会被扩展。如果你向前插入一个元素，所有元素都将向右移动1个位置，这是非常昂贵的。

- LWChris

Answer 3

你可以通过在线阅读有关Python列表的文章来确认这一点。Python将列表实现为数组，其中数组的大小实际上通常比当前列表的大小要大。未使用的元素位于数组的末尾，表示可以添加到列表末尾的新元素，而不是开头。Python使用经典的摊销成本方法，因此如果您进行了一堆附加操作，则平均而言，在列表末尾附加需要O（1）时间，尽管偶尔会出现单个附加导致数组变满，因此需要创建一个新的更大的数组，并将所有数据复制到新数组中。另一方面，如果您始终在列表的开头插入，则在底层数组中，所有元素都需要向右移动一个索引以腾出空间，以便在数组的开头插入新元素。因此，总结一下，如果您通过N次插入创建一个列表，则如果您始终将新项目附加到列表末尾，总运行时间将为O（N），如果您始终附加到列表前面，则总运行时间将为O（N ^ 2）。

- user2566092