最近有读者发了一条私信,希望我介绍一下 Python 列表和字典在读写数据的时候谁更快。
那就安排一下,我们先来介绍列表和字典的底层实现,如果了解了具体的实现,那么一切问题就都迎刃而解了。我准备分多篇文章介绍,本次先来介绍列表。
在初学列表的时候,可能书上会告诉你列表就是一个大仓库,什么都可以存放。但我们要知道,无论是 Python 的变量,还是列表、元组里面的元素,它们本质上都是一个指针。
并且根据我们使用列表的经验,可以得出以下两个结论:
而列表在底层由PyListObject结构体表示,定义于头文件 Include/listobject.h 中:
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
我们看到里面有如下成员:
PyObject_VAR_HEAD:变长对象的公共头部信息,包含了以下三个字段;
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 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_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
# 显然 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 即可。
以上就是列表和字典的区别,我们下一篇文章再介绍字典是怎么实现的,加深一遍印象。
崔庆才的新书《Python3网络爬虫开发实战(第二版)》已经正式上市了!书中详细介绍了零基础用 Python 开发爬虫的各方面知识,同时相比第一版新增了 JavaScript 逆向、Android 逆向、异步爬虫、深度学习、Kubernetes 相关内容,同时本书已经获得 Python 之父 Guido 的推荐,目前本书正在七折促销中!
内容介绍:《Python3网络爬虫开发实战(第二版)》内容介绍
扫码购买