Python 列表内存预分配问题

以下例子均的运行环境为 Python 3.9.5,不同版本的实际运行结果可能有所不同

前言

前端时间看了 Golang 的 学习了一下 数组 和 Slice,其中 Slice 相当于动态数组,其中数组的长度是固定的,而 Slice 则是不定长的。在 Python 中是没有数组和 Slice 的概念,它们可以通通归类为 List(列表),那么问题来了,定长的 List 和 不定长的 List 在表现上会有区别吗?(这里的定长的 List 是指对 List 进行初始化,也就是所谓的预分配)
接下来通过几个例子去验证这个问题。

实验过程

首先验证一下 空列表 以及在不断新增元素的情况下 List 的 size 的变化

1
2
3
4
5
6
7
8
9
from sys import getsizeof

l = []

print(f'空列表:{getsizeof(l)}')

for i in range(10):
l.append(l)
print(f'存在{i+1}元素的列表:{getsizeof(l)}')

看一下输出结果

1
2
3
4
5
6
7
8
9
10
11
空列表:56
存在1元素的列表:88
存在2元素的列表:88
存在3元素的列表:88
存在4元素的列表:88
存在5元素的列表:120
存在6元素的列表:120
存在7元素的列表:120
存在8元素的列表:120
存在9元素的列表:184
存在10元素的列表:184

从上面的运行结果可以发现,其实 List 也存在一定的扩容机制的,列表初始化过程中将会申请一个存储四个元素的存储区,当存储区填满时,列表会再次申请四个存储空间存储元素。当元素量达到原存储空间的两倍时,列表会再次申请原来旧的存储空间的两倍的容量存储元素。

不管任何语言在一旦进行扩容操作必然会存在:
1. 重新申请内存
2. 复制老数组到新的内存
3. 回收老数组的内存

上面的过程如果出现的次数比较频繁必然会导致运行速度的降低,那么究竟会降低多少呢?

例子

以下例子运行环境为 ipython

没有任何处理的例子

1
2
3
4
%%timeit
l=[]
for i in range(1000):
l.append(i)

运行结果如下:

预分配后的列表

1
2
3
4
5
6
%%timeit
size = 1000
l = [None] * size

for i in range(size):
l[i] = i

和上面唯一不同的是,我们在遍历之前,给列表 l 预先分配了一个长度为 1000 的 None 的空数组,运行结果如下:

从这两个例子不难看出,如果预先知道要使用数组的大小,并且对列表进行初始化的话,是可以在一定程度上提高运行效率的。

结尾

上面的例子,如果使用列表推导式速度会更快。

列表预先配可能并不适合复杂场景,但是一旦有符合这个特殊场景的情况下效果应该是蛮不错的。