Python列表对象实现原理详解

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;
}

创建过程大致是:

  1. 检查size参数是否有效,如果小于0,直接返回NULL,创建失败
  2. 检查size参数是否超出Python所能接受的大小,如果大于PY_SIZE_MAX(64位机器为8字节,在32位机器为4字节),内存溢出。
  3. 检查缓冲池free_list是否有可用的对象,有则直接从缓冲池中使用,没有则创建新的PyListObject,分配内存。
  4. 初始化ob_item中的元素的值为Null
  5. 设置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对象内存的占用空间会根据列表长度的变化而调整。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • python实现对象列表根据某个属性排序的方法详解

    本文实例讲述了python实现对象列表根据某个属性排序的方法.分享给大家供大家参考,具体如下: 对于一个已有的python list, 里面的内容是一些对象,这些对象有一些相同的属性值, 在一些特定的情况下,需要自己选择特定的排序,也就是根据某一个具体的属性来排序,在网上找了下资料,一般来说有两种方法,但从根本上来说,还是调用了list.sort 方法来实现.下面是简单的测试代码片段: #coding:utf-8 class Person: def __init__(self,name,age,

  • Python为何不能用可变对象作为默认参数的值

    先来看一道题目: >>> def func(numbers=[], num=1): ... numbers.append(num) ... return numbers >>> func() [1] >>> func() [1, 1] >>> func() [1, 1, 1] 我们似乎发现了一个Bug,每次用相同的方式调用函数 func() 时,返回结果竟然不一样,而且每次返回的列表在不断地变长. >>> id(fu

  • Python3实现的字典、列表和json对象互转功能示例

    本文实例讲述了Python3实现的字典.列表和json对象互转功能.分享给大家供大家参考,具体如下: python3可以使用json模块操作json json.dumps(): 对json进行编码,对应php的json_encode() json.loads(): 对json进行解码,对应php的json_decode() test.py #!/usr/bin/python3 import json #python字典类型转换为json对象 data = { 'id' : 1, 'name' :

  • python实现比较类的两个instance(对象)是否相等的方法分析

    本文实例讲述了python实现比较类的两个instance(对象)是否相等的方法.分享给大家供大家参考,具体如下: 对于同一个Class,可以创建不同的实例(instance), 如何比较这两个 instance 是否相等呢?我们知道,对于计算机来说,要判断两个对象是否相等,就是看在内存中的地址是否同一个.如果内存地址一样,那么肯定是相等的.这种情况通常出现在一个对象是另外一个对象的引用时出现. 但在实际的开发过程中,要比较两个对象是否相等,并不是通过内存地址来判断的,而是通过这两个对象的部分属

  • Python字典对象实现原理详解

    字典类型是Python中最常用的数据类型之一,它是一个键值对的集合,字典通过键来索引,关联到相对的值,理论上它的查询复杂度是 O(1) : >>> d = {'a': 1, 'b': 2} >>> d['c'] = 3 >>> d {'a': 1, 'b': 2, 'c': 3} 在字符串的实现原理文章中,曾经出现过字典对象用于intern操作,那么字典的内部结构是怎样的呢?PyDictObject对象就是dict的内部实现. 哈希表 (HASH TA

  • Python列表对象实现原理详解

    Python中的列表基于PyListObject实现,列表支持元素的插入.删除.更新操作,因此PyListObject是一个变长对象(列表的长度随着元素的增加和删除而变长和变短),同时它还是一个可变对象(列表中的元素根据列表的操作而发生变化,内存大小动态的变化),PyListObject的定义: typedef struct { # 列表对象引用计数 int ob_refcnt; # 列表类型对象 struct _typeobject *ob_type; # 列表元素的长度 int ob_siz

  • Python字符串对象实现原理详解

    在Python世界中将对象分为两种:一种是定长对象,比如整数,整数对象定义的时候就能确定它所占用的内存空间大小,另一种是变长对象,在对象定义时并不知道是多少,比如:str,list, set, dict等. >>> import sys >>> sys.getsizeof(1000) 28 >>> sys.getsizeof(2000) 28 >>> sys.getsizeof("python") 55 >&

  • Python整数对象实现原理详解

    整数对象在Python内部用PyIntObject结构体表示: typedef struct { PyObject_HEAD long ob_ival; } PyIntObject; PyObject_HEAD宏中定义的两个属性分别是: int ob_refcnt; struct _typeobject *ob_type; 这两个属性是所有Python对象固有的: ob_refcnt:对象的引用计数,与Python的内存管理机制有关,它实现了基于引用计数的垃圾收集机制 ob_type:用于描述P

  • Python字典底层实现原理详解

    在Python中,字典是通过散列表或说哈希表实现的.字典也被称为关联数组,还称为哈希数组等.也就是说,字典也是一个数组,但数组的索引是键经过哈希函数处理后得到的散列值.哈希函数的目的是使键均匀地分布在数组中,并且可以在内存中以O(1)的时间复杂度进行寻址,从而实现快速查找和修改.哈希表中哈希函数的设计困难在于将数据均匀分布在哈希表中,从而尽量减少哈希碰撞和冲突.由于不同的键可能具有相同的哈希值,即可能出现冲突,高级的哈希函数能够使冲突数目最小化.Python中并不包含这样高级的哈希函数,几个重要

  • Python列表常用函数使用详解

    目录 介绍  append() extend() insert() pop() remove() 介绍  append() 语法 list.append( element ) 参数 element:任何类型的元素 列表「末尾」添加元素 name_list = ['zhangsan', 'lisi', 'wangwu'] name_list.append('zhaoliu') print(name_list) 输出: ['zhangsan', 'lisi', 'wangwu', 'zhaoliu'

  • Python图像处理之边缘检测原理详解

    目录 原理 Sobel检测算子 Laplacian算子 算子比较 原理 边缘检测是图像处理和计算机视觉当中的基本问题,边缘检测的目的是标识数字图像中亮度变化明显的点,图像的边缘检测可以大幅度的减少数据量,并且剔除了可以认为不相关的信息,保留了图像重要的结构属性,它们绝大多数可以分为两类:基于搜索和基于零穿越. 基于搜索:通过寻找图像一阶导数中max来检测边界,然后利用计算结果估计边缘的局部方向,通常采用梯度的方向,并在此方向找到局部梯度模的最大值,代表的算法是Sobel算子和Scharr算子.

  • python super用法及原理详解

    这篇文章主要介绍了python super用法及原理详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 概念 super作为python的内建函数.主要作用如下: 允许我们避免使用基类 跟随多重继承来使用 实例 在单个继承的场景下,一般使用super来调用基类来实现: 下面是一个例子: class Mammal(object): def __init__(self, mammalName): print(mammalName, 'is a wa

  • Python模块future用法原理详解

    这篇文章主要介绍了Python模块future用法原理详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 计算机的知识太多了,很多东西就是一个使用过程中详细积累的过程.最近遇到了一个很久关于future的问题,踩了坑,这里就做个笔记,免得后续再犯类似错误. future的作用:把下一个新版本的特性导入到当前版本,于是我们就可以在当前版本中测试一些新版本的特性.说的通俗一点,就是你不用更新python的版本,直接加这个模块,就可以使用python

  • Python日志syslog使用原理详解

    这篇文章主要介绍了Python日志syslog使用原理详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 syslog的官方说明在: https://docs.python.org/2/library/syslog.html#module-syslog 该模块的主要方式为: #!/usr/bin/python # -*- coding: utf-8 -*- import syslog syslog.openlog([ident[, logopt

随机推荐