Python 中列表的实现

原文链接
这篇文章描述了列表对象的 CPython 实现。CPython 是最常见的一种 Python 实现。

列表在 Python 中很强大，下面让我们来看下它的内部是如何实现的。

来看下面简单的程序，在列表中添加一些整数并把它们打印出来。

>>> l = []
>>> l.append(1)
>>> l.append(2)
>>> l.append(3)
>>> l
[1, 2, 3]
>>> for e in l:
...     print(e)
...
1
2
3

正如你所看到的那样，列表是可以迭代的。

列表对象的 C 结构

在 CPython 中列表是用下面的 C 语言结构来表示的。ob_item是一个用来保存元素指针的数组。allocated是分配的内存大小。

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

列表初始化

让我们来看下当初始化一个空 list 的时候发生了什么。例如l = []。

arguments: size of the list = 0
returns: list object = []
PyListNew:
    nbytes = size * size of global Python object = 0
    allocate new list object
    allocate list of pointers (ob_item) of size nbytes = 0
    clear ob_item
    set list's allocated var to 0 = 0 slots
    return list object

非常重要的是知道列表申请内存空间的大小（后文用 allocated 代替）和列表实际存储元素所占空间的大小 (size) 之间的区别，size的大小和len(l)是一样的，而allocated的大小是在内存中已经申请的空间大小。通常情况下allocated的值要比size大，这是为了避免每次有新元素加入列表时都要调用realloc进行内存分配，接下来我们会看到更多这方面的内容。

Append

我们在列表中追加一个整数：l.append(1)。发生了什么？内部的 C 函数app1()被调用了：

arguments: list object, new element
returns: 0 if OK, -1 if not
app1:
    n = size of list
    call list_resize() to resize the list to size n+1 = 0 + 1 = 1
    list[n] = list[0] = new element
    return 0

让我们看下list_resize()，它会申请多余的内存空间来避免自身被过多调用，列表的扩容模式如下：0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …

arguments: list object, new size
returns: 0 if OK, -1 if not
list_resize:
    new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) = 3
    new_allocated += newsize = 3 + 1 = 4
    resize ob_item (list of pointers) to size new_allocated
    return 0

新分配了四个内存空间来存放元素，第一个空间存放整数 1。你可以从下图中看出 l[0] 指向我们刚才追加的整数对象。虚线框代表已经分配但是还没有被使用的内存空间。

Append 操作的时间复杂度为O(1)。

我们继续新增一个元素：l.append(2)。list_resize被调用，列表存储元素的大小 n 增加 1 变为 2，但由于分配的内存空间是 4，没有必要再去分配更多的内存空间。同理，我们再次新增两个整数也是一样：l.append(3)，l.append(4)。下图展示了到目前为止我们做了什么。

Insert

让我们在索引为 1 的位置插入一个整数 5：l.insert(1, 5)，并观察以下内部发生了什么，ins1()被调用了：

arguments: list object, where, new element
returns: 0 if OK, -1 if not
ins1:
    resize list to size n+1 = 5 -> 4 more slots will be allocated
    starting at the last element up to the offset where, right shift each element
    set new element at offset where
    return 0

虚线框代表已经分配但是还没有被使用的内存空间。上图最右边，申请了 8 个内存空间但是列表实际存储元素或者说列表的长度只有 5 个内存空间。

Insert 操作的复杂度是O(n)。

Pop

当你弹出最后一个元素时：l.pop()，listpop()会被调用，list_resize会在listpop()内部被调用并且如果弹出元素后的size小于分配的内存空间的一半，这时列表会缩小内存空间。

arguments: list object
returns: element popped
listpop:
    if list empty:
        return null
    resize list with size 5 - 1 = 4. 4 is not less than 8/2 so no shrinkage
    set list object size to 4
    return last element

Pop 操作的复杂度是O(1)。

你可以发现索引 4 的位置还指向那个被弹出的整数，但很重要的是，列表的 size 已经变成了 4。

让我们再弹出一个元素。在list_resize内部，size – 1 = 4 – 1 = 3，比已经分配的内存空间的一半还要小。所以 list 的申请空间缩小到
6 个，list 的实际使用空间现在是 3 个。

你可以发现（下图）索引 3 和 4 的位置还指向一些整数，但是列表的实际使用（存储元素）的空间却只有 3 个了。

Remove

Python 的列表对象有一个方法来移除指定元素：l.remove(5)，此时listremove()会被调用：

arguments: list object, element to remove
returns none if OK, null if not
listremove:
    loop through each list element:
        if correct element:
            slice list between element's slot and element's slot + 1
            return none
    return null

为了删除元素，list_ass_slice()会被调用，我们来看看它是怎么起作用的。在这里，当我们移除索引位置为 1 的元素 5 时，上面代码中的 element’s slot and element’s slot + 1 分别是 1 和 2：

arguments: list object, low offset, high offset
returns: 0 if OK
list_ass_slice:
    copy integer 5 to recycle list to dereference it
    shift elements from slot 2 to slot 1
    resize list to 5 slots
    return 0

Remove 操作的复杂度是O(n)。

核心部分

我们能看到 Python 设计者的苦心。在需要的时候扩容，但又不允许过度的浪费，适当的内存回收是非常必要的。

这个确定调整后的空间大小算法很有意思。
调整后大小 (new_allocated) = 新元素数量 (newsize) + 预留空间 (new_allocated)
调整后的空间肯定能存储 newsize 个元素。要关注的是预留空间的增长状况。
将预留算法改成 Python 版就更清楚了：(newsize // 8) + (3 if newsize < 9 else 6)。
当 newsize >= allocated，自然按照这个新的长度 “扩容” 内存。

而如果 newsize < allocated，且利用率低于一半呢?

很显然，这个新长度小于原来的已分配空间长度，自然会导致 realloc 收缩内存。