Python列表对象实现原理详解
作者:FOOFISH-PYTHON之禅 发布时间:2022-09-07 10:24:58
Python中的列表基于PyListObject实现,列表支持元素的插入、删除、更新操作,因此PyListObject是一个变长对象(列表的长度随着元素的增加和删除而变长和变短),同时它还是一个可变对象(列表中的元素根据列表的操作而发生变化,内存大小动态的变化),PyListObject的定义:
typedef struct {
# 列表对象引用计数
int ob_refcnt;
# 列表类型对象
struct _typeobject *ob_type;
# 列表元素的长度
int ob_size; /* Number of items in variable part */
# 真正存放列表元素容器的指针,list[0] 就是 ob_item[0]
PyObject **ob_item;
# 当前列表可容纳的元素大小
Py_ssize_t allocated;
} PyListObject;
咋一看PyListObject对象的定义非常简单,除了通用对象都有的引用计数(ob_refcnt)、类型信息(ob_type),以及变长对象的长度(ob_size)之外,剩下的只有ob_item,和allocated,ob_item是真正存放列表元素容器的指针,专门有一块内存用来存储列表元素,这块内存的大小就是allocated所能容纳的空间。alloocated是列表所能容纳的元素大小,而且满足条件:
0 <= ob_size <= allocated
len(list) == ob_size
ob_item == NULL 时 ob_size == allocated == 0
列表对象的创建
PylistObject对象的是通过函数PyList_New创建而成,接收参数size,该参数用于指定列表对象所能容纳的最大元素个数。
// 列表缓冲池, PyList_MAXFREELIST为80
static PyListObject *free_list[PyList_MAXFREELIST];
//缓冲池当前大小
static int numfree = 0;
PyObject *PyList_New(Py_ssize_t size)
{
PyListObject *op; //列表对象
size_t nbytes; //创建列表对象需要分配的内存大小
if (size < 0) {
PyErr_BadInternalCall();
return NULL;
}
/* Check for overflow without an actual overflow,
* which can cause compiler to optimise out */
if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
return PyErr_NoMemory();
nbytes = size * sizeof(PyObject *);
if (numfree) {
numfree--;
op = free_list[numfree];
_Py_NewReference((PyObject *)op);
} else {
op = PyObject_GC_New(PyListObject, &PyList_Type);
if (op == NULL)
return NULL;
}
if (size <= 0)
op->ob_item = NULL;
else {
op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
if (op->ob_item == NULL) {
Py_DECREF(op);
return PyErr_NoMemory();
}
memset(op->ob_item, 0, nbytes);
}
# 设置ob_size
Py_SIZE(op) = size;
op->allocated = size;
_PyObject_GC_TRACK(op);
return (PyObject *) op;
}
创建过程大致是:
检查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方法中:
static void
list_dealloc(PyListObject *op)
{
Py_ssize_t i;
PyObject_GC_UnTrack(op);
Py_TRASHCAN_SAFE_BEGIN(op)
if (
i = Py_SIZE(op);
while (--i >= 0) {
Py_XDECREF(op->ob_item[i]);
}
PyMem_FREE(op->ob_item);
}
if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
free_list[numfree++] = op;
else
Py_TYPE(op)->tp_free((PyObject *)op);
Py_TRASHCAN_SAFE_END(op)
}
当PyListObject对象被销毁的时候,首先将列表中所有元素的引用计数减一,然后释放ob_item占用的内存,只要缓冲池空间还没满,那么就把该PyListObject加入到缓冲池中(此时PyListObject占用的内存并不会正真正回收给系统,下次创建PyListObject优先从缓冲池中获取PyListObject),否则释放PyListObject对象的内存空间。
列表元素插入
设置列表某个位置的值时,如“list[1]=0”,列表的内存结构并不会发生变化,而往列表中插入元素时会改变列表的内存结构:
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
// n是列表元素长度
Py_ssize_t i, n = Py_SIZE(self);
PyObject **items;
if (v == NULL) {
PyErr_BadInternalCall();
return -1;
}
if (n == PY_SSIZE_T_MAX) {
PyErr_SetString(PyExc_OverflowError,
"cannot add more objects to list");
return -1;
}
if (list_resize(self, n+1) == -1)
return -1;
if (where < 0) {
where += n;
if (where < 0)
where = 0;
}
if (where > n)
where = n;
items = self->ob_item;
for (i = n; --i >= where; )
items[i+1] = items[i];
Py_INCREF(v);
items[where] = v;
return 0;
}
相比设置某个列表位置的值来说,插入操作要多一次PyListObject容量大小的调整,逻辑是list_resize,其次是挪动where之后的元素位置。
// newsize: 列表新的长度
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated;
Py_ssize_t allocated = self->allocated;
if (allocated >= newsize && newsize >= (allocated >> 1)) {
assert(self->ob_item != NULL || newsize == 0);
Py_SIZE(self) = newsize;
return 0;
}
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
PyErr_NoMemory();
return -1;
} else {
new_allocated += newsize;
}
if (newsize == 0)
new_allocated = 0;
items = self->ob_item;
if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))
PyMem_RESIZE(items, PyObject *, new_allocated);
else
items = NULL;
if (items == NULL) {
PyErr_NoMemory();
return -1;
}
self->ob_item = items;
Py_SIZE(self) = newsize;
self->allocated = new_allocated;
return 0;
}
满足 allocated >= newsize && newsize >= (allocated /2)时,简单改变list的元素长度,PyListObject对象不会重新分配内存空间,否则重新分配内存空间,如果newsize<allocated/2,那么会减缩内存空间,如果newsize>allocated,就会扩大内存空间。当newsize==0时内存空间将缩减为0。
总结
PyListObject缓冲池的创建发生在列表销毁的时候。
PyListObject对象的创建分两步:先创建PyListObject对象,然后初始化元素列表为NULL。
PyListObject对象的销毁分两步:先销毁PyListObject对象中的元素列表,然后销毁PyListObject本身。
PyListObject对象内存的占用空间会根据列表长度的变化而调整。
来源:https://foofish.net/python-list-implements.html
猜你喜欢
- 本文只是几年前学习的tkinter的时候写的测试程序,十分之简陋,只是学习用,没什么其他用处。学习一下莫烦Python的tkinter教程,
- 1.算法描述:(1)共循环 n-1 次(2)每次循环中,如果 前面的数大于后面的数,就交换(3)设置一个标签,如果上次没有交换,就说明这个是
- 前面提到了银行转账这个场景,展示了一个比较耗时的转账操作。这篇继续转帐,下面展示一段程序,多个线程的操作都更改了amount变量导致运行结果
- 如下所示:年月日时分秒>>> print datetime.datetime.now().strftime("%
- 注入漏洞代码和分析<?php function customError($errno, $errstr, $errfile, $err
- 有使用过VS2005开发工具的朋友或者其他语句如js中都有Try catch 语句块,那么在mysql中是否能有SQLserver的@@er
- 方法一:<script language="JavaScript"> <!--
- 鉴于最近复习线性代数计算量较大,且1800答案常常忽略一些逆阵、行列式的计算答案,故用Python写出矩阵的简单计算程序,便于检查出错的步骤
- 一、界面介绍文件导航区域 能够 浏览/定位/打开 项目文件文件编辑区域 能够 编辑 当前打开的文件控制台区域 能够:输出程序执行内容跟踪调试
- 最近由于要毕业了写论文做毕设,然后还在实习发现已经好久都没有写博客了。今天由于工作需求,需要用Django实现单用户登录。大概意思就是跟QQ
- 首先需要安装Win32-ODBC模块,具体的步骤如下:1:从TOOLS栏目中下载Win32-ODBC.zip,下载完后用winzip解开到一
- 一直在用JS写ASP,也不是特别原因,只是当初学的是JS,后来学ASP时知道ASP也可以用JS写,就没去学VBS.前几个月刚学ASP的时候找
- 实验环境:windows 7,anaconda 3(python 3.5),tensorflow(gpu/cpu)函数介绍:所用函数为six
- Python pip安装lxml出错的问题解决办法1. 在使用pip安装lxml过程中出现了一下错误: &
- 你好,我是林骥。斜率图,可以快速展现两组数据之间各维度的变化,特别适合用于对比两个时间点的数据。比如说,为了对比分析某产品不同功能的用户满意
- Javascript是网页制作中离不开的脚本语言,依靠它,一个网页的内容才生动活泼、富有朝气。但也许你还没有发现并应用它的一些更高级的功能吧
- 学生信息系统提示:python编写的学生成绩管理系统,包括8个功能和打包教程一、功能界面 def menum():
- 人脸美白原理人脸美白原理说透了,就是一种图像的颜色空间处理,所以我们需要通过颜色空间进行设计。不过,我们先来参考以下PS对于图像美白的处理步
- 不知道做网络程序的朋友是否重视COOKIES作用域对于多域名或 主域与WWW二级域名同时共用一站点,设置Cookies的作用域,让整个网站用
- 使用MySQL,安全问题不能不注意。以下是MySQL提示的23个注意事项:1.如果客户端和服务器端的连接需要跨越并通过不可信任的网络,那么就