深度解密 Python 列表的实现原理

发表于 2年以前 | 总阅读数：709 次

楔子

最近有读者发了一条私信，希望我介绍一下 Python 列表和字典在读写数据的时候谁更快。

那就安排一下，我们先来介绍列表和字典的底层实现，如果了解了具体的实现，那么一切问题就都迎刃而解了。我准备分多篇文章介绍，本次先来介绍列表。

列表是怎么实现的？

在初学列表的时候，可能书上会告诉你列表就是一个大仓库，什么都可以存放。但我们要知道，无论是 Python 的变量，还是列表、元组里面的元素，它们本质上都是一个指针。

并且根据我们使用列表的经验，可以得出以下两个结论：

每个列表的元素个数可以不一样，所以这是一个变长对象；
可以对列表的元素进行添加、删除、修改等操作，所以这是一个可变对象；

而列表在底层由PyListObject结构体表示，定义于头文件 Include/listobject.h 中：

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

我们看到里面有如下成员：

PyObject_VAR_HEAD：变长对象的公共头部信息，包含了以下三个字段；
ob_refcnt：对象的引用计数；
ob_type：对象的类型；
ob_size：负责维护变长对象的长度，比如 len(列表) 的时候，会直接返回这里的 ob_size；
ob_item：一个二级指针，指向 PyObject * 类型的指针数组，这个指针数组保存的便是对象的指针，而操作底层数组都是通过 ob_item 来进行操作的；
allocated：容量，我们知道列表底层是使用了 C 的数组，而底层数组的长度就是列表的容量；

列表之所以要有容量的概念，是因为列表可以动态添加和删除元素，但是底层的数组在创建完毕之后，其长度却是固定的。所以一旦添加新元素的时候，发现数组已满，这时候只能申请一个更长的数组，同时把旧数组中的元素依次拷贝到新数组里面（这一过程就是列表的扩容），然后再将新元素添加进去，最后再将旧数组释放掉。

但是问题来了，总不可能每添加一个元素，就申请一次数组、将所有元素都拷贝一次吧。所以列表在扩容的时候，会将数组申请的长一些，可以在添加元素的时候不用每次都申请新的数组。

这便是列表的底层结构示意图，我们看到底层数组的长度为 5，说明此时列表的容量为 5，但是里面只有 3 个 PyObject * 指针，说明列表的 ob_size 是 3，或者说列表里面此时有 3 个元素。

如果这个时候往列表中 append 一个元素，那么会将这个新元素设置在数组索引为 ob_size 的位置、或者说索引为 3 的位置。一旦设置完，ob_size 会自动加 1，因为 ob_size 要和列表的长度保持一致。

如果此时再往列表中 append 一个元素的话，那么还是将新元素设置在索引为 ob_size 的位置，此时也就是索引为 4 的位置。然后 ob_size 加 1，变成 5。

列表的容量是 5，但此时长度也达到了 5，这说明当下一次 append 的时候，已经没有办法再容纳新的元素了。因为此时列表的长度、或者说元素个数已经达到了容量。当然最直观的还是这里的底层数组，很明显全都占满了。那这个时候如果想再接收新元素的话，要怎么办呢？显然只能扩容了。

原来的容量是 5，长度也是 5，当再来一个新元素的时候由于没有位置了，所以要扩容。但是扩容的时候肯定会将容量申请的大一些、即底层数组申请的长一些。

而申请的新的底层数组长度是9，那么说明列表的容量就变成了 9。然后将原来数组中的 PyObject * 按照顺序依次拷贝到新的数组里面，并让 ob_item 指向新的数组。然后将新元素设置在新数组中索引为 ob_size 的位置、即索引为 5 的位置，再将 ob_size 加 1（此时 ob_size 变成了 6）。

以上便是列表底层在扩容的时候所经历的过程。

并且通过以上几张图，我们可以得知列表在append之后地址是不变的。因为如果长度没有达到容量，那么 append 其实就是往底层数组中设置了一个新元素；如果达到容量了，那么会扩容，但扩容只是申请一个新的指针数组，然后让 ob_item 重新指向罢了。

所以底层的指针数组会变，但 PyListObject 结构体实例本身是没有变化的。因此列表执行 append, extend, pop, insert 的时候，因为是本地操作，所以它的地址是不会变化的。

下面我们再来看看列表所占的内存大小是怎么算的：

PyObject_VAR_HEAD：24字节；
ob_item：8 字节；
allocated：8 字节；

所以总共 40 字节，但是不要忘记，在计算列表大小的时候，ob_item 指向的指针数组也要算在内。所以：列表的大小 = 40 + 8 * 指针数组长度(或者说列表容量)。注意是指针数组长度、或者说列表容量，可不是列表长度，因为数组一旦申请了，不管你用没用，大小就摆在那里了。就好比你租了间房子，就算不住，房租该交还是得交。

# 显然一个空数组占40个字节
print([].__sizeof__())  # 40

# 40 + 3 * 8 = 64
print([1, 2, "x" * 1000].__sizeof__())  # 64
#虽然里面有一个长度为1000的字符串
#但我们说列表存放的都是指针，所以大小都是8字节

#注意: 我们通过lst = [1, 2, 3]这种方式创建列表的话
#不管内部元素有多少个, 其ob_size和allocated都是一样的
#只有当列表在添加元素的时候，发现容量不够了才会扩容
lst = list(range(10))
# 40 + 10 * 8 = 120
print(lst.__sizeof__())  # 120
# 这个时候append一个元素
lst.append(123)
print(lst.__sizeof__())  # 184
#我们发现大小达到了184, (184 - 40) // 8 = 18
#说明扩容之后申请的数组的长度为18

所以列表的大小我们就知道是怎么来的了，以及为什么列表在通过索引定位元素的时候，时间复杂度是 O(1)。因为列表存储的都是对象的指针，不管对象有多大，其指针大小是固定的，都是 8 字节。通过索引可以瞬间计算出偏移量，从而找到对应元素的指针，而操作指针会自动操作指针所指向的内存。

print([1, 2, 3].__sizeof__())  # 64
print([[1, 2, 3]].__sizeof__())  # 48

相信上面这个结果，你肯定能分析出原因。因为第一个列表中有3个指针，所以大小是40 + 24 = 64；而第二个列表中有一个指针，所以是40 + 8 = 48。用一张图来展示一下[1, 2, 3]和[[1, 2, 3]]的底层结构，看看它们之间的区别：

到此相信你已经彻底掌握列表的结构了，下面我们来分析一下列表相关操作的时间复杂度。

添加元素

假设有如下这样一个列表：

我们来看一下它在添加元素的时候，是怎么表现的。

首先添加元素有很多种方式，其中 append 方法用于向尾部追加一个元素，看一下它的底层实现。

static PyObject *
list_append(PyListObject *self, PyObject *object)
{  
    //显然调用的app1是核心, 它里面实现了添加元素的逻辑
    //Py_RETURN_NONE是一个宏，表示返回Python中的None
    //因为list.append返回的就是None
    if (app1(self, object) == 0)
        Py_RETURN_NONE;
    return NULL;
}

static int
app1(PyListObject *self, PyObject *v)
{  
    //参数self是列表，v是要添加的元素
    //获取列表的长度
    Py_ssize_t n = PyList_GET_SIZE(self);
    //......
    //因为v作为了列表的一个元素，所以其指向的对象的引用计数要加1
    Py_INCREF(v);
    //设置元素，原来的列表长度为n，最大索引是n - 1
    //那么追加的话就等于将元素设置在索引为n的地方
    PyList_SET_ITEM(self, n, v);
    return 0;
}

以上就是 append 的逻辑，所谓插入、追加本质上都是先计算出索引，然后再通过索引设置元素。

如果上面的列表 append 一个 6，就会变成如下：

还是很好理解的。

添加元素除了 append，还可以使用 insert，和只能在尾部追加的 append 不同，该方法可以在任意位置插入。

static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{  
    /*
    参数self：列表
    参数where：索引
    参数v：插入的值
    */

    //i是循环变量，n则是当前列表的元素个数
    Py_ssize_t i, n = Py_SIZE(self);
    //指向指针数组的二级指针
    PyObject **items;
    //......
    //确定插入位置
    if (where < 0) {
        //如果where小于0，则加上 n
        //比如有6个元素，where=-1，那么会加上6，得到5
        //显然就是insert在索引为5的位置上 
        where += n;
        //如果吃撑了，写个 -100，加上元素的个数还是小于0
        if (where < 0)
            //那么where = 0，就在开头插入
            where = 0;
    }
    //如果where > n，那么就在索引为n的位置插入，
    //可元素个数为n，最大索引是n-1啊
    //对，所以此时就相当于append
    if (where > n)
        where = n;
    //走到这，索引就确定完了，然后是设置元素
    //拿到原来的二级指针，指向一个指针数组
    items = self->ob_item;
    //然后从where处开始，把索引为i的值赋值给索引为i+1
    //相当于元素后移
    //既然是在where处插入，那么where之前的就不需要动了
    //所以到where处就停止了
    for (i = n; --i >= where; )
        items[i+1] = items[i];
    //增加v指向的对象的引用计数，因为要被放到列表里
    Py_INCREF(v);
    //将索引为where的值设置成v
    items[where] = v;
    return 0;
}

逻辑不难理解，然后是时间复杂度。

append：显然时间复杂度为 O(1)，只是在指定位置写入一个元素。但需要注意：如果容量不够了，那么会扩容，而扩容是一个 O(n) 操作。因此 append 最坏情况下也是一个 O(n) 操作，只不过扩容不会频繁发生，所以 append 方法的平均时间复杂度还是O(1)。
insert：平均时间复杂度是 O(n)，因为从插入位置开始的每一个元素，都要向后移动；
extend：这个我们没有说，但也能够猜到，它的时间复杂度和 append 是一样的；

获取元素

列表支持基于索引获取元素，这个就比较简单了。直接拿到底层的指针数组，然后基于索引获取即可，所以它是一个时间复杂度为 O(1) 的操作。

当然除了索引，还可以使用切片，只不过切片在底层仍然使用了索引。

# lst[1: 8: 3] 等价于
start = 1
end = 8
step = 3
while start < end:
    item = lst[start]
    # .....
    start += step

因此一些看似高端的操作，在底层实际上并没有那么神秘。

设置元素

我们可以获取指定索引的元素，当然也可以对其进行设置。

# 获取元素
item = lst[5]
# 设置元素
lst[5] = item

前面说了，添加元素本质上也是通过设置元素实现的。如果列表最大索引为 n，那么 append 就等价于在 n + 1 的地方设置元素；而 insert 则是先将待插入位置后面的元素依次后移，然后再将待插入位置设置成指定的元素，本质上也是在不断地设置元素。

而设置元素的时间复杂度显然也是 O(1)，当然对一个已存在的元素进行设置，就等价于修改。

另外在设置元素的时候，除了使用索引，还可以使用切片。而在使用切片的时候非常灵活，我们通过 Python 演示一下。

lst = [1, 2, 3, 4, 5, 6, 7, 8]

#首先通过切片进行设置的话
#右值一定要是一个可迭代对象
lst[0: 3] = [11, 22, 33]
# 会将lst[0]设置为11、lst[1]设置为22、lst[2]设置为33
print(lst)  # [11, 22, 33, 4, 5, 6, 7, 8]

#而且它们的长度可以不相等
#这里表示将[0: 3]的元素设置为[1, 2]
#其中lst[0]设置成1, lst[1]设置成2
#问题来了, lst[2]咋办? 
#由于右值中已经没有元素与之匹配了, 那么lst[2]就会被删掉
lst[0: 3] = [1, 2]
print(lst)  # [1, 2, 4, 5, 6, 7, 8]

#所以如果想删除[0: 3]的元素，那么只需要执行lst[0: 3] = []即可
#因为[]里面没有元素能与之匹配，所以lst中[0: 3]的位置由于匹配不到
#那么相当于执行了删除操作，当然由于Python的动态特性，
#lst[0: 3] = []、lst[0: 3] = ()、lst[0: 3] = "
#都是可以的
lst[0: 3] = ""
print(lst)  # [5, 6, 7, 8]
#实际上我们del lst[0]的时候，就是执行了lst[0: 1] = []

# 当然如果右值元素多的话也是可以的
lst[0: 1] = [1, 2, 3, 4]
print(lst)  # [1, 2, 3, 4, 6, 7, 8]
#将lst[0]设置为1很好理解, 但此时左边已经结束了
#所以剩余的元素会依次插在后面


#然后重点来了, 如果切片有步长的话, 那么两边一定要匹配
#由于此时lst中有7个元素, lst[:: 2]会得到4个元素
#那么右边的可迭代对象的长度也必须是4
lst[:: 2] = ['a', 'b', 'c', 'd']
print(lst)  # ['a', 2, 'b', 4, 'c', 7, 'd']

# 但是，如果长度不一致
try:
    lst[:: 2] = ['a', 'b', 'c']
except Exception as e:
    # 显然会报错
    print(e)  
# attempt to assign sequence of size 3 to extended slice of size 4

理解起来应该不难，建议去源码 listobject.c 中看一下具体实现，而在查看的时候，有以下几个函数，要牢牢地抓住。

list_subscript：获取元素时，会调用此函数；
list_ass_subscript：设置元素时，会调用此函数；

然后这两个函数即可以接收索引，也可以接收切片：

获取元素时传入的是索引，那么list_subscript内部会调用list_item；传入的是切片，那么内部会调用list_slice。
设置元素时传入的是索引，那么list_ass_subscript内部会调用list_ass_item；传入的是切片，那么会调用list_ass_slice。并且list_ass_slice虽然是设置元素，但删除元素也是调用的它，比如通过 lst[n:n+1]=[] 便可删除索引为n的元素。事实上remove、pop方法都只是计算出待删除元素的索引，真正的删除操作还是通过list_ass_slice来执行的。
另外当传入切片时，只有步长为 1，才会调用list_slice和list_ass_slice；如果步长不为1，那么就采用循环的方式逐个遍历。

以上就是 Python 在设置元素时的具体实现，虽然是设置元素，但添加和删除用的也是它。

删除元素

删除元素可以使用 pop，默认从尾部弹出元素，当然我们也可以指定索引，弹出指定的元素。

而我们说了 pop 和 del 在删除元素的时候，会调用 list_ass_slice。

lst = [1, 2, 3, 4, 5]

# 修改元素，在底层相当于修改指针数组中索引为 4 的元素
lst[4] = 55
print(lst)
"""
[1, 2, 3, 4, 55]
"""

# 添加元素，本质上是将元素设置在索引为 5 的位置
# 但我们不能执行 lst[5] = 6，因为索引越界了
# 需要调用 append，由解释器帮我们设置
lst.append(6)
print(lst)
"""
[1, 2, 3, 4, 55, 6]
"""

# 删除索引为 3 的元素
# 可以执行 del lst[3] 或者 lst.pop(3)
# 但它们底层都等价于如下
lst[3: 4] = []
print(lst)
"""
[1, 2, 3, 55, 6]
"""

Python 解释器是用 C 实现的，而 C 是一门很单纯的语言，所以列表的一些花里胡哨的功能回归到 C，就是一些对 C 数组的简单操作罢了。

列表的扩容

前面说过，当添加元素时，可能会发生容量不够的情况，因此列表在执行 append 和 insert 方法的时候，都会先检测列表已存储的元素个数是否已达到当前容量。一旦达到，那么要先进行扩容。

而在 list_resize 里面，它的扩容机制是这样的。

我们来验证一下：

lst = [0] * 1000
# 长度和容量一致
print(len(lst))
print((lst.__sizeof__() - 40) // 8)
"""
1000
1000
"""
# 再必须提一下
# 扩容是当解释器在添加元素时，发现容量不够的时候才会扩容
# 而使用 lst = [...] 这种方式创建的列表
# 其大小和容量是相等的

# 但此时添加一个元素的话, 那么ob_size会变成1001，大于容量1000
# 所以此时列表就要扩容了, 执行 list_resize
# (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
# 显然 newsize 就是 1001
print(
    1001 + (1001 >> 3) + (3 if 1001 < 9 else 6)
)  # 1132

# append一个元素，列表扩容
lst.append(123)
print((lst.__sizeof__() - 40) // 8)  # 1132

结果是一样的，因为底层就是这么实现的，所以结果必须一样。只不过我们通过这种测试的方式证明了这一点，也加深了对列表的认识。

介绍完扩容，再来介绍缩容，因为列表元素个数要是远小于容量的话，也要进行缩容，否则就会出现内存浪费。那什么时候缩容呢？答案是当列表的元素个数小于容量的一半时就会缩容。

举个生活中的例子，假设你租了10间屋子用于办公，显然你要付10间屋子的房租，不管你有没有用，一旦租了肯定是要付钱的。同理底层数组也是一样，只要你申请了，不管有没有存储元素，内存已经占用了。

但有一天你用不到10间屋子了，假设要用8间或者9间，那么会让剩余的屋子闲下来。但由于退租比较麻烦，并且只闲下来一两间屋子，所以干脆就不退了，还是会付10间屋子的钱，这样没准哪天又要用的时候就不用重新租了。

对于列表也是如此，在删除元素（相当于屋子不用了）的时候，如果发现长度还没有低于容量的一半，那么也不会缩容。但反之就要缩容了，比如屋子闲了8间，也就是只需要两间屋子就足够了，那么此时肯定要退租了，闲了8间，可能会退掉6间。

lst = [0] * 1000
print(len(lst))
print((lst.__sizeof__() - 40) // 8)
"""
1000
1000
"""

# 删除500个元素, 此时长度或者说ob_size就为500
lst[500:] = []
# 但是ob_size还是达到了容量的一半, 所以不会缩容
print(len(lst))
print((lst.__sizeof__() - 40) // 8)
"""
500
1000
"""

# 如果再删除一个元素的话, 那么就要进行缩容了
# 因为 ob_size 变成了 499, 小于 1000 // 2
# 缩容之后容量怎么算呢? 还是之前那个公式
print(499 + (499 >> 3) + (3 if 499 < 9 else 6))
"""
567
"""

# 测试一下, 删除一个元素
# 看看会不会按照我们期待的规则进行缩容
lst.pop()
print(len(lst))
print((lst.__sizeof__() - 40) // 8)
"""
499
567
"""

一切都和我们想的是一样的，因为源码中就是这么写的。

最后在源码中还有一个 if 判断，就是当列表长度为 0 的时候，那么缩容之后的容量也会是 0。

lst = [0] * 1000

lst[:] = []
print(
    len(lst), (lst.__sizeof__() - 40) // 8
)  # 0 0

# 如果按照之前的容量变化公式的话, 会发现结果应该是3
# 但是结果是0, 就是因为多了if判断
# 如果newsize是0, 就把容量也设置为0
print(0 + (0 >> 3) + (3 if 0 < 9 else 6))  # 3

为什么要这么做呢？因为 Python 认为，列表长度为 0 的话，说明你不想用这个列表了，所以多余的 3 个也没有必要申请了。还以租房为例，如果你一间屋子都不用了，说明你可能不用这里的屋子办公了，因此直接全部退掉。

小结

以上就是列表的底层实现以及相关操作，这里再来总结一下。

1）列表在基于索引获取和设置元素时，时间复杂度是 O(1)，这个效率是极高的，比字典还要快一点。因为字典在基于 key 操作 value 的时候，也是先对 key 进行哈希，然后映射出一个索引，再基于索引查找。所以哈希表本质上也是一个数组。

我们看到在查找元素时，列表比字典还要快那么一点点。因为这两者在 C 的层面都是基于数组实现的，只不过列表是直接基于索引获取，而字典则需要多一步对 key 进行映射的过程。当然这两者的效率都是极高的，复杂度都是 O(1)。

2）列表可以调用 append 追加元素，它的时间复杂度也是 O(1)，只是偶尔会伴随着扩容。append 的效率也是极高的，比字典写入元素的效率还要快一点点。

列表写入 100万个元素需要 8.01ms，而字典写入 100万个键值对需要 9.97ms。当然两者单次写入没有太大区别，毕竟复杂度都是 O(1)。但列表添加元素使用的要不是 append，而是 insert，那速度就会变慢，因为它的时间复杂度是 O(n)。

3）因此，如果是基于索引操作的话，那么列表是没有任何问题的，但问题在于索引只是一个单纯的数字罢了。我们上面举的例子中，列表的索引和对应元素是相等的，但在工作中我们并不知道某个元素位于列表中的哪个位置，这个时候就只能靠遍历的方式了。

import time
import numpy as np

def test(count: int, value: int):
    """
    :param count: 循环次数
    :param value: 查询的元素
    :return:
    """
    # 包含一千个随机数的列表
    lst = list(np.random.randint(0, 2 ** 30, size=1000))
    # 基于列表构建一个字典
    d = dict.fromkeys(lst)

    # 查询元素value是否在列表中, 循环count次, 并统计时间
    t1 = time.perf_counter()
    for _ in range(count):
        value in lst
    t2 = time.perf_counter()
    print("列表查询耗时:", round(t2 - t1, 2))

    # 查询元素value是否在字典中, 循环count次, 并统计时间
    t1 = time.perf_counter()
    for _ in range(count):
        value in d
    t2 = time.perf_counter()
    print("字典查询耗时:", round(t2 - t1, 2))


# 分别查询一千次、一万次、十万次、二十万次
test(10 ** 3, 22333)
"""
列表查询耗时: 0.13
字典查询耗时: 0.0
"""
test(10 ** 4, 22333)
"""
列表查询耗时: 1.22
字典查询耗时: 0.0
"""
test(10 ** 5, 22333)
"""
列表查询耗时: 12.68
字典查询耗时: 0.01
"""
test(10 ** 5 * 2, 22333)
"""
列表查询耗时: 25.72
字典查询耗时: 0.01
"""

字典的查询速度非常快，从测试中我们看到，随着循环次数越来越多，列表所花费的总时间越来越长。但是字典由于查询所花费的时间极少，查询速度非常快，所以即便循环 20 万次，花费的总时间也不过才 0.01 秒左右。

此外字典还有一个特点，就是它的快不会受到数据量的影响，从含有一万个键值对的字典中查找，和从含有一千万个键值对的字典中查找，两者花费的时间几乎是没有区别的。

原因就是字典在查找元素的时候也是使用了数组的索引，而对于数组来说，基于索引查询第 0 个元素和第 100w 个元素也是没有区别的，都是 O(1)。所以字典才会这么快，并且不受数据量的影响。

但对于当前来说，列表它不是通过索引来判断元素是否存在的，而是遍历每一个元素，然后和指定的元素进行比较。此时它的复杂度就是 O(n)，因此遍历次数越多，耗时越长。

4）最后是删除元素，无论是基于索引删除，还是通过 remove 删除，时间复杂度都是 O(n)，因为涉及数据的移动或者比较。而字典仍是 O(1)，字典在删除元素的时候实际上是伪删除，只需要将对应的键值对标记为 DUMMY 即可。

以上就是列表和字典的区别，我们下一篇文章再介绍字典是怎么实现的，加深一遍印象。