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

            
typedef struct {
# 列表對(duì)象引用計(jì)數(shù)
int ob_refcnt; 
# 列表類型對(duì)象 
struct _typeobject *ob_type;
# 列表元素的長(zhǎng)度
int ob_size; /* Number of items in variable part */
# 真正存放列表元素容器的指針，list[0] 就是 ob_item[0]
PyObject **ob_item;
# 當(dāng)前列表可容納的元素大小
Py_ssize_t allocated;
} PyListObject;
          

咋一看PyListObject對(duì)象的定義非常簡(jiǎn)單，除了通用對(duì)象都有的引用計(jì)數(shù)（ob_refcnt）、類型信息（ob_type），以及變長(zhǎng)對(duì)象的長(zhǎng)度（ob_size）之外，剩下的只有ob_item，和allocated，ob_item是真正存放列表元素容器的指針，專門有一塊內(nèi)存用來(lái)存儲(chǔ)列表元素，這塊內(nèi)存的大小就是allocated所能容納的空間。alloocated是列表所能容納的元素大小，而且滿足條件：

• 0 <= ob_size <= allocated
• len(list) == ob_size
• ob_item == NULL 時(shí) ob_size == allocated == 0

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

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

            
// 列表緩沖池, PyList_MAXFREELIST為80
static PyListObject *free_list[PyList_MAXFREELIST];
//緩沖池當(dāng)前大小
static int numfree = 0;
PyObject *PyList_New(Py_ssize_t size)
{
PyListObject *op; //列表對(duì)象
size_t nbytes; //創(chuàng)建列表對(duì)象需要分配的內(nèi)存大小
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);
}
# 設(shè)置ob_size
Py_SIZE(op) = size;
op->allocated = size;
_PyObject_GC_TRACK(op);
return (PyObject *) op;
}
          

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

1. 檢查size參數(shù)是否有效，如果小于0，直接返回NULL，創(chuàng)建失敗
2. 檢查size參數(shù)是否超出Python所能接受的大小，如果大于PY_SIZE_MAX（64位機(jī)器為8字節(jié)，在32位機(jī)器為4字節(jié)），內(nèi)存溢出。
3. 檢查緩沖池free_list是否有可用的對(duì)象，有則直接從緩沖池中使用，沒有則創(chuàng)建新的PyListObject，分配內(nèi)存。
4. 初始化ob_item中的元素的值為Null
5. 設(shè)置PyListObject的allocated和ob_size。

PYLISTOBJECT對(duì)象的緩沖池

free_list是PyListObject對(duì)象的緩沖池，其大小為80，那么PyListObject對(duì)象是什么時(shí)候加入到緩沖池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)
}
          

當(dāng)PyListObject對(duì)象被銷毀的時(shí)候，首先將列表中所有元素的引用計(jì)數(shù)減一，然后釋放ob_item占用的內(nèi)存，只要緩沖池空間還沒滿，那么就把該P(yáng)yListObject加入到緩沖池中（此時(shí)PyListObject占用的內(nèi)存并不會(huì)正真正回收給系統(tǒng)，下次創(chuàng)建PyListObject優(yōu)先從緩沖池中獲取PyListObject），否則釋放PyListObject對(duì)象的內(nèi)存空間。

列表元素插入

設(shè)置列表某個(gè)位置的值時(shí)，如“l(fā)ist[1]=0”，列表的內(nèi)存結(jié)構(gòu)并不會(huì)發(fā)生變化，而往列表中插入元素時(shí)會(huì)改變列表的內(nèi)存結(jié)構(gòu)：

            
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
// n是列表元素長(zhǎng)度
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;
}
          

相比設(shè)置某個(gè)列表位置的值來(lái)說(shuō)，插入操作要多一次PyListObject容量大小的調(diào)整，邏輯是list_resize，其次是挪動(dòng)where之后的元素位置。

            
// newsize： 列表新的長(zhǎng)度
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)時(shí)，簡(jiǎn)單改變list的元素長(zhǎng)度，PyListObject對(duì)象不會(huì)重新分配內(nèi)存空間，否則重新分配內(nèi)存空間，如果newsize allocated，就會(huì)擴(kuò)大內(nèi)存空間。當(dāng)newsize==0時(shí)內(nèi)存空間將縮減為0。

總結(jié)

• PyListObject緩沖池的創(chuàng)建發(fā)生在列表銷毀的時(shí)候。
• PyListObject對(duì)象的創(chuàng)建分兩步：先創(chuàng)建PyListObject對(duì)象，然后初始化元素列表為NULL。
• PyListObject對(duì)象的銷毀分兩步：先銷毀PyListObject對(duì)象中的元素列表，然后銷毀PyListObject本身。
• PyListObject對(duì)象內(nèi)存的占用空間會(huì)根據(jù)列表長(zhǎng)度的變化而調(diào)整。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。