Python列表對象實現(xiàn)原理詳解

更新時間：2019年07月01日 10:15:25 作者：FOOFISH-PYTHON之禪

這篇文章主要介紹了Python列表對象實現(xiàn)原理詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下

Python中的列表基于PyListObject實現(xiàn)，列表支持元素的插入、刪除、更新操作，因此PyListObject是一個變長對象（列表的長度隨著元素的增加和刪除而變長和變短），同時它還是一個可變對象（列表中的元素根據列表的操作而發(fā)生變化，內存大小動態(tài)的變化），PyListObject的定義：

typedef struct {
# 列表對象引用計數(shù)
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對象的定義非常簡單，除了通用對象都有的引用計數(shù)（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

列表對象的創(chuàng)建

PylistObject對象的是通過函數(shù)PyList_New創(chuàng)建而成，接收參數(shù)size，該參數(shù)用于指定列表對象所能容納的最大元素個數(shù)。

// 列表緩沖池, 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; //創(chuàng)建列表對象需要分配的內存大小
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;
}

創(chuàng)建過程大致是：

檢查size參數(shù)是否有效，如果小于0，直接返回NULL，創(chuàng)建失敗
檢查size參數(shù)是否超出Python所能接受的大小，如果大于PY_SIZE_MAX（64位機器為8字節(jié)，在32位機器為4字節(jié)），內存溢出。
檢查緩沖池free_list是否有可用的對象，有則直接從緩沖池中使用，沒有則創(chuàng)建新的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對象被銷毀的時候，首先將列表中所有元素的引用計數(shù)減一，然后釋放ob_item占用的內存，只要緩沖池空間還沒滿，那么就把該PyListObject加入到緩沖池中（此時PyListObject占用的內存并不會正真正回收給系統(tǒng)，下次創(chuàng)建PyListObject優(yōu)先從緩沖池中獲取PyListObject），否則釋放PyListObject對象的內存空間。

列表元素插入

設置列表某個位置的值時，如“l(fā)ist[1]=0”，列表的內存結構并不會發(fā)生變化，而往列表中插入元素時會改變列表的內存結構：

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。