分享一下Python list的空间分配公式

Oct. 22, 2018, 10:11 p.m.

我主要想分享一下list的动态特点,动态是如何体现的,list和我们了解的基础数据结构中的数组有什么不一样的地方。

我们知道数组的扩容需要重新申请一块内存空间,然后把数据搬移过去,然后再释放旧的空间,每增加一次,搬一次,这个操作的代价有点重,可能你会说,可以选择链表啊,链表天生就支持扩容,没错

毕竟数组和链表是基础的数据结构嘛,只是定义了最基础最基础的情况,它是可以杂交的嘛,可以进行升级的嘛。list既然选择了数组来进行改造,肯定是需要它的优点,然后改良它的缺点。

我们先看下list中元素的数量和它被分配空间的大小

import sys

my_list = []
sys.getsizeof(my_list)  # 元素数量为0个时,大小为64字节
64

my_list.append('a')
sys.getsizeof(my_list)  
# 元素数量为1个时,开始扩容
# 如果你想避免第1次扩容,可以避免初始化一个空list,更推荐的做法是使用列表推导式
96

my_list.append('a')
sys.getsizeof(my_list)
96

my_list.append('a')
sys.getsizeof(my_list)
96

my_list.append('a')
sys.getsizeof(my_list)  
# 元素数量为1-4个时,my_list的空间大小不变,都是96个字节
96

my_list.append('a')
sys.getsizeof(my_list)  
# 元素数量为5个时,my_list开始扩容
128

从上面的数据,我们可以看出,list是通过预先分配好一些空间,来避免每次都进行数据搬移

  • 当需要添加4个元素时,原来需要搬移4次,现在只需要1次了,性能提升得非常明显
  • 当你只有2个元素时,多出来的2个空间不会被使用,就会浪费

那么list是每4个元素就扩容一次吗,当然不是,它是有一个空间分配公式的

M = (N >> 3) + (N < 9 ? 3: 6)
# M为增加的容量大小,N为元素的数量

N  0 1-4  5-8  9-16  17-25  26-35  ..  991-1120
- - - - - - - - - - - - - - - - - - - - - - - -
M  0   3    3     5      8     9  ..        129

当N的值为0, 1, 2, 3, 4, 5, 6, 7时,M = 3

这里不是元素数量每变化一次就扩容一次

而是当N=M时,才会通过当前N的值去计算M的值,然后就扩容M个大小的容量

总结

  • 在元素的数量很小时,比如20以内,由于额外分配的空间很小,可以忽略不计
  • 如果元素的数量很大时,比如500万,根据空间分配公式,额外分配的空间是62.5万+6
  • 如果数据是通过不断的添加达到一个很大的规模的,因为在不断添加的过程中,会多次触发扩容,可以通过分析应用代码,来总结出数据添加的规律,然后可以考虑使用tuple来进行替代
  • list是一个使用频率非常高数据类型,了解了这些“内幕”,在对list进行操作的时候,就会有点感觉,知道list的背后都在做些什么
  • 可以防止一些不合理和无知的使用
  • 在需要优化的时候,清楚可以优化的内容
  • python的list也称为over-allocate的数组,意思就是多分配空间的数组
  • 分享几个list操作的基本教程

  • Built-in Types - list — Python 3.6.9 documentation

  • Python 列表(List) | 菜鸟教程

运行环境

  • Python:3.6
  • 个人计算机:iMac
  • 处理器:2.9GHz 四核
  • 内存:8GB
  • software:Jupyter

返回首页