Python源码剖析(五)列表对象

Python源码剖析(五)列表对象bilibili 视频讲解 https space bilibili com b 站用户名 平凡的久月 1 PyListObject 变长对象 数据长度在定义时是不知道的 只能在创建时才能确定 与字符串对象不同的是支持插入删除操作 运行时动态地调整其维护的内存和元素

大家好,我是讯享网,很高兴认识大家。

1. PyListObject

变长对象(数据长度在定义时是不知道的,只能在创建时才能确定)

与字符串对象不同的是支持插入删除操作,运行时动态地调整其维护的内存和元素

与C++中的Vector(动态顺序表,连续的空间)很相似,与list(带头节点的双向循环链表)反而不像

可变对象(改变值内存地址不会发生改变)

1.1 定义

// Include/listobject.h #ifndef Py_LIMITED_API typedef struct { 
    PyObject_VAR_HEAD /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */ PyObject **ob_item; // 指向元素列表所在的内存块的首地址 /* ob_item contains space for 'allocated' elements. The number * currently in use is ob_size. * Invariants: * 0 <= ob_size <= allocated * len(list) == ob_size * ob_item == NULL implies ob_size == allocated == 0 * list.sort() temporarily sets allocated to -1 to detect mutations. * * Items must normally not be NULL, except during construction when * the list is not yet visible outside the function that builds it. */ Py_ssize_t allocated; // 可容纳的元素的总数 } PyListObject; #endif 

讯享网
讯享网#define PyObject_VAR_HEAD PyVarObject ob_base; typedef struct { 
    PyObject ob_base; Py_ssize_t ob_size; /* Number of items in variable part */ } PyVarObject; 

ob_size与allocated是什么关系?

都与内存管理有关系,实际使用的内存数量记录在ob_size中。(类似C++中Vevtor的size与capacity)

PyTypeObject PyList_Type = { 
    PyVarObject_HEAD_INIT(&PyType_Type, 0) "list", sizeof(PyListObject), 0, (reprfunc)list_repr, /* tp_repr */ 0, /* tp_as_number */ &list_as_sequence, /* tp_as_sequence */ &list_as_mapping, /* tp_as_mapping */ // ....... (initproc)list___init__, /* tp_init */ PyType_GenericAlloc, /* tp_alloc */ PyType_GenericNew, /* tp_new */ PyObject_GC_Del, /* tp_free */ }; 

1.2 创建PyListObject

Python只提供了唯一的路径创建PyListObject对象

  • PyList_New(Py_ssize_t size)


    讯享网

    讯享网PyObject * PyList_New(Py_ssize_t size) { 
          PyListObject *op; #ifdef SHOW_ALLOC_COUNT static int initialized = 0; if (!initialized) { 
          Py_AtExit(show_alloc); initialized = 1; } #endif if (size < 0) { 
          PyErr_BadInternalCall(); return NULL; } // 检查缓冲池中是否有可用对象 // 第一次创建PyListObject对象时,绕过这个机制,直接调用PyObject_GC_New创建对象 // 问题:缓冲池中的对象从哪里来的? if (numfree) { 
          numfree--; op = free_list[numfree]; _Py_NewReference((PyObject *)op); #ifdef SHOW_ALLOC_COUNT count_reuse++; #endif } else { 
          // 两部分:PyListObject+其维护的元素列表的内存首地址 // 通过ob_item建立联系 // 与垃圾回收机制也有关系 op = PyObject_GC_New(PyListObject, &PyList_Type); if (op == NULL) return NULL; #ifdef SHOW_ALLOC_COUNT count_alloc++; #endif } if (size <= 0) op->ob_item = NULL; else { 
          op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *)); if (op->ob_item == NULL) { 
          Py_DECREF(op); return PyErr_NoMemory(); } } Py_SIZE(op) = size; op->allocated = size; _PyObject_GC_TRACK(op); return (PyObject *) op; } 

在这里插入图片描述

1.3 List的增删改查

本质就是顺序表的增删改查

1.3.1 增加元素

list[3] = "Huamanlou" 
讯享网int PyList_SetItem(PyObject *op, Py_ssize_t i, PyObject *newitem) { 
    PyObject **p; // 类型检查 if (!PyList_Check(op)) { 
    Py_XDECREF(newitem); PyErr_BadInternalCall(); return -1; } // 索引的有效性检查 if (i < 0 || i >= Py_SIZE(op)) { 
    Py_XDECREF(newitem); PyErr_SetString(PyExc_IndexError, "list assignment index out of range"); return -1; } // 设置元素 p = ((PyListObject *)op) -> ob_item + i; // 处理“创实际块”为空的情况 Py_XSETREF(*p, newitem); return 0; } 

1.3.2 插入元素

list.insert(2, "Huamanlou") 

顺序表的元素插入:会移动后面的所有元素

与增加元素的区别:插入元素的动作有可能导致ob_item指向的内存发生变化。

讯享网static int ins1(PyListObject *self, Py_ssize_t where, PyObject *v) { 
    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; } // 保证有足够内存:(1)不需要重新申请;(2)重新申请 if (list_resize(self, n+1) < 0) return -1; // 确定插入点:Python支持负索引,灵活(但也有代价,得处理负数的情况) if (where < 0) { 
    where += n; if (where < 0) where = 0; } // 与C++中的Vector的内存管理机制类似 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; } 

1.3.3 追加元素append

注意:追加在第ob_szie+1个位置,即list[ob_size] = “py”。

1.3.4 删除元素

一一匹配,等值删除,后面元素一一前移。

static int list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v) { 
    // ...... } //  

1.4 列表对象缓冲池

缓冲池中的缓冲对象是从哪里来的?

讯享网static void list_dealloc(PyListObject *op) { 
    Py_ssize_t i; PyObject_GC_UnTrack(op); Py_TRASHCAN_SAFE_BEGIN(op) // 销毁list对象维护的PyObject对象 if (op->ob_item != NULL) { 
    /* Do it backwards, for Christian Tismer. There's a simple test case where somehow this reduces thrashing when a *very* large list is created and immediately deleted. */ i = Py_SIZE(op); while (--i >= 0) { 
    Py_XDECREF(op->ob_item[i]); } PyMem_FREE(op->ob_item); } // 销毁list自身,并放进缓冲池 if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op)) free_list[numfree++] = op; else Py_TYPE(op)->tp_free((PyObject *)op); Py_TRASHCAN_SAFE_END(op) } 

思考:能不能保留list维护的PyObject对象的内存?

引用计数,类似Py2中大整数对象缓冲池(公用一些内存)。

小讯
上一篇 2025-02-09 23:52
下一篇 2025-03-24 12:18

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/131258.html