Python 列表前置时间复杂度

Question

为什么是这段代码

res = []
for i in range(10000):
    res[0:0] = [i]

大约比这段代码快十倍？

res = []
for i in range(10000):
    res = [i] + res

我预计两者都必须移动所有现有列表元素以将新整数放在零索引处。随着范围的变化，两者看起来确实都是 O(n^2)，但切片赋值比添加快得多，这意味着后者的基本操作数量大约是后者的 10 倍。

(是的，两者都无法有效地实现此结果，最好使用 deque 或 append 然后反转结果)

Answer 1

你是对的，在高层次上，循环以相同的方式计算本质上相同的结果。因此，时间差异是由于所用 Python 版本的实现细节所致。没有语言的属性可以解释这种差异。

在 python.org C 实现 (CPython) 中，代码实际上在底层是完全不同的。

res[0:0] = [i]

做它看起来做的事 ;-) res 的全部内容向右移动一个插槽，i 插入左侧创建的孔中结尾。对平台 C 库的 memmove() 函数的一次调用消耗了大量时间，该函数一次性完成转换。现代硬件和 C 库非常擅长快速移动连续的内存片(在 C 级别，Python 列表对象就是)。

res = [i] + res

在幕后做的更多，这主要是由于 CPython 的引用计数。它更像是:

create a brand new list object
stuff `i` into it
for each element of `res`, which is a pointer to an int object:
    copy the pointer into the new list object
    dereference the pointer to load the int object's refcount
    increment the refcount
    store the new refcount back into the int object
bind the name `res` to the new list object
decrement the refcount on the old `res` object
at which point the old res's refcount becomes 0 so it's trash
so for each object in the old res:
    dereference the pointer to load the int object's refcount
    decrement the refcount
    store the new refcount back into the int object
    check to see whether the new refcount is zero
    take the "no, it isn't zero" branch
release the memory for the old list object

更多的原始工作，所有指针取消引用都可以跳过整个内存，这对缓存不友好。

执行

res[0:0] = [i]

跳过大部分内容:它从一开始就知道仅仅移动 res 内容的位置不能对移动对象的引用计数进行任何净更改，因此不会费心去增加或减少任何这些 refcounts。 C 级的 memmove() 几乎就是一团蜡，指向 int 对象的指针都不需要取消引用。不仅原始工作更少，而且对缓存非常友好。