怎么在Python中實現列表對象

今天就跟大家聊聊有關怎么在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。

看完上述內容，你們對怎么在Python中實現列表對象有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注億速云行業資訊頻道，感謝大家的支持。