Python列表对象实现原理

新媒体管家

关键时刻,第一时间送达!

Python中的列表基于PyListObject实现,列表支持元素的插入、删除、更新操作,因此PyListObject是一个变长对象(列表的长度随着元素的增加和删除而变长和变短),同时它还是一个可变对象(列表中的元素根据列表的操作而发生变化,内存大小动态的变化)。

PyListObject的定义:

咋一看PyListObject对象的定义非常简单,除了通用对象都有的引用计数(ob_refcnt)、类型信息(ob_type),以及变长对象的长度(ob_size)之外,剩下的只有ob_item,和allocated,ob_item是真正存放列表元素容器的指针,专门有一块内存用来存储列表元素,这块内存的大小就是allocated所能容纳的空间。

alloocated是列表所能容纳的元素大小,而且满足条件:

0

len(list) == ob_size

ob_item == NULL 时 ob_size == allocated == 0

列表对象的创建

PylistObject对象的是通过函数PyList_New创建而成,接收参数size,该参数用于指定列表对象所能容纳的最大元素个数。

创建过程大致是:

检查size参数是否有效,如果小于0,直接返回NULL,创建失败

检查size参数是否超出Python所能接受的大小,如果大于PY_SIZE_MAX(64位机器为8字节,在32位机器为4字节),内存溢出。

检查缓冲池free_list是否有可用的对象,有则直接从缓冲池中使用,没有则创建新的PyListObject,分配内存。

初始化ob_item中的元素的值为Null

设置PyListObject的allocated和ob_size。

PyListObject对象的缓冲池

free_list是PyListObject对象的缓冲池,其大小为80,那么PyListObject对象是什么时候加入到缓冲池free_list的呢?答案在list_dealloc方法中:

当PyListObject对象被销毁的时候,首先将列表中所有元素的引用计数减一,然后释放ob_item占用的内存,只要缓冲池空间还没满,那么就把该PyListObject加入到缓冲池中(此时PyListObject占用的内存并不会正真正回收给系统,下次创建PyListObject优先从缓冲池中获取PyListObject),否则释放PyListObject对象的内存空间。

列表元素插入

设置列表某个位置的值时,如“list[1]=0”,列表的内存结构并不会发生变化,而往列表中插入元素时会改变列表的内存结构:

相比设置某个列表位置的值来说,插入操作要多一次PyListObject容量大小的调整,逻辑是list_resize,其次是挪动where之后的元素位置。

满足allocated >= newsize && newsize >= (allocated /2)时,简单改变list的元素长度,PyListObject对象不会重新分配内存空间,否则重新分配内存空间,如果newsizeallocated,就会扩大内存空间。当newsize==0时内存空间将缩减为0。

总结

PyListObject缓冲池的创建发生在列表销毁的时候。

PyListObject对象的创建分两步:先创建PyListObject对象,然后初始化元素列表为NULL。

PyListObject对象的销毁分两步:先销毁PyListObject对象中的元素列表,然后销毁PyListObject本身。

PyListObject对象内存的占用空间会根据列表长度的变化而调整。

参考:

listobject.h

listobject.c

来自:LiuZhiJun

https://foofish.net/python-list-implements.html

程序员共读整理发布,转载请联系作者获得授权

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20171221B0RDD800?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券