python list 底层实现

本篇文章描述了 CPython 中 list 的实现方式。

C 语言用结构体表示 List 对象

C 语言使用结构体实现 list 对象,结构体代码如下。

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item; //指向 list 中的对象
    Py_ssize_t allocated; //内存分配的插槽
} PyListObject;

List 初始化

I = [] 为例

list 的数量是指 len(l)。分配的槽位数量是指在内存中实际分配的数量。通常情况,内存中分配的数量要大于 list 的数量。这是为了当添加新元素时,避免内存再分配。

Append

当运行l.append(1)时, CPython 将调用app1()

list_resize() 会故意分配更多的内存,避免被多次调用。分配内存大小增加:0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …

第一次分配了 4 个槽位,I[0] 指向了数字对象 1 。正方形虚线表示未使用过的槽位。追加操作的均摊复杂度为 O(1) 。

均摊时间复杂度是平均时间复杂度的一种,是一种简化的计算方法。

image

继续追加元素:l.append(2)。调用 list_resize 实现 n + 1 = 2。由于分配了四个空间,不需要分配内存。当再向列表追加两个数字时,l.append(3), l.append(4),如下图如示:

Python lists

Insert

在位置 1 插入整型 5 ,即调用 python 的 l.insert(1, 5) 。CPython 会调用 ins1()

插入操作需要将剩余元素向右迁移:

image

上图虚线表示未使用的槽位(slots),分配了 8 个槽位,但 list 的长度只有 5 。 insert 的时间复杂度为 O(n)。

pop

弹出列表的最后一个元素使用 l.pop(),CPython 使用 listpop() 实现这个过程。如果新内存大小少于分配大小的一半, listpop() 将调用 list_resize 减少 list 内存。

Pop 的时间复杂度是 O(1)。

image

注意,此时槽位 4 仍然指向整型 4 ,但是 list 的大小却是 4 。只有 pop 更多的元素才能调用 list_resize() 减少内存,如果再 pop 一个元素, size - 1 = 4 - 3 = 3, 3 小于分配槽位的一半 8/2 = 4 。所以 list 收缩到 6 个槽位, list 的大小为 3 。虽然槽位 3 和 4 依旧指向整型对象,但是整体大小变成了 3 。

image

remove

Python 可以用 remove 删除指定元素:l.remove(5)。此时将调用 listremove()

CPython 调用 list_ass_slice() 函数对列表进行切分并删除元素。当在位置 1 移除元素 5 时,低偏移(low offset)是 1 ,高偏移(high offset)是 2 :

remove 时间复杂度是 O(n)。

文章参考:

http://www.laurentluce.com/posts/python-list-implementation/