软件测试 | Python 中 list 的底层实现方式

本篇文章描述了 CPython 中 list 的实现方式。原文链接：https://ceshiren.com/t/topic/10916

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

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

代码语言：txt复制

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) 。

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

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

Insert

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

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

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

pop

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

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

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

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/

自动化测试 python

0 人点赞