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进行任何净更改，因此不会费心增加或减少任何这些refcounts。 C级memmove()几乎就是整个蜡球，并且没有任何指向int对象的指针需要被解除引用。不仅原始工作少，而且非常缓存友好。

Answer 2

在每个示例的相关行上运行反汇编，我们得到以下字节码：

res[0:0] = [i]

  4          25 LOAD_FAST                1 (i)
             28 BUILD_LIST               1
             31 LOAD_FAST                0 (res)
             34 LOAD_CONST               2 (0)
             37 LOAD_CONST               2 (0)
             40 BUILD_SLICE              2
             43 STORE_SUBSCR

res = [i] + res

  4          25 LOAD_FAST                1 (i)
             28 BUILD_LIST               1
             31 LOAD_FAST                0 (res)
             34 BINARY_ADD
             35 STORE_FAST               0 (res)

在第一个例子（切片）中没有完成BINARY_ADD，只进行了存储操作，并且在添加的情况下不仅存储操作，还有一个BINARY_ADD操作，它做了很多，这可能是为什么它慢得多。虽然切片表示法确实需要构建切片，但这些操作也非常简单。

为了更公平的比较，我们可以通过查找来替换切片符号，如果它是预构造和存储的（使用像s = slice(0, 0)这样的东西）;结果字节码如下所示：

res[s] = [i]

  4          25 LOAD_FAST                1 (i)
             28 BUILD_LIST               1
             31 LOAD_FAST                0 (res)
             34 LOAD_GLOBAL              1 (s)
             37 STORE_SUBSCR

这使得它具有相同数量的字节码指令计数，现在我们只看到加载和存储指令，而具有+操作的指令有效地需要额外的指令。