8

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

为什么是这样？在操作方面，向头部插入一个元素似乎并没有那么昂贵。

4

3 回答 3

11

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

这些方法的时间复杂度在此处详细记录。

我引用：

在内部，列表表示为数组；最大的成本来自超出当前分配大小的增长（因为所有内容都必须移动），或者来自在开头附近的某个位置插入或删除（因为之后的所有内容都必须移动）。

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

于 2013-07-14T01:45:17.057 回答
1

在 Python 中，列表被实现为数组。如果将一个元素附加到数组，则数组的保留空间会被简单地扩展。如果你添加一个元素，所有元素都会移动 1，这是非常昂贵的。

于 2013-07-14T01:52:20.293 回答
1

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

于 2013-07-14T01:57:53.673 回答