Py学习  »  Python

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

进击的Coder • 1 年前 • 649 次点击  
这是「进击的Coder」的第 751 篇技术分享
作者:古明地觉
来源:古明地觉的编程教室

阅读本文大概需要 13 分钟。




楔子



最近有读者发了一条私信,希望我介绍一下 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([12"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([123].__sizeof__())  # 64
print([[123]].__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     item = lst[start]
    # .....
    start += step

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



设置元素



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

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

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

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

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

lst = [12345678]

#首先通过切片进行设置的话
#右值一定要是一个可迭代对象
lst[03] = [112233]
# 会将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[03] = [12]
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[03] = ""
print(lst)  # [5, 6, 7, 8]
#实际上我们del lst[0]的时候,就是执行了lst[0: 1] = []

# 当然如果右值元素多的话也是可以的
lst[01] = [1234]
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_slicelist_ass_slice如果步长不为1,那么就采用循环的方式逐个遍历。


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



删除元素



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

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

lst = [12345]

# 修改元素,在底层相当于修改指针数组中索引为 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[34] = []
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 
# 显然 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(02 ** 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 ** 322333)
"""
列表查询耗时: 0.13
字典查询耗时: 0.0
"""

test(10 ** 422333)
"""
列表查询耗时: 1.22
字典查询耗时: 0.0
"""

test(10 ** 522333)
"""
列表查询耗时: 12.68
字典查询耗时: 0.01
"""

test(10 ** 5 * 222333)
"""
列表查询耗时: 25.72
字典查询耗时: 0.01
"""

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

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

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


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


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


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


End

崔庆才的新书《Python3网络爬虫开发实战(第二版)》已经正式上市了!书中详细介绍了零基础用 Python 开发爬虫的各方面知识,同时相比第一版新增了 JavaScript 逆向、Android 逆向、异步爬虫、深度学习、Kubernetes 相关内容,‍同时本书已经获得 Python 之父 Guido 的推荐,目前本书正在七折促销中!

内容介绍:《Python3网络爬虫开发实战(第二版)》内容介绍



扫码购买






点个在看你最好看

Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/149432
 
649 次点击