Python中的列表基于PyListObject實現(xiàn)，列表支持元素的插入、刪除、更新操作，因此PyListObject是一個變長對象（列表的長度隨著元素的增加和刪除而變長和變短），同時它還是一個可變對象（列表中的元素根據(jù)列表的操作而發(fā)生變化，內(nèi)存大小動態(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是真正存放列表元素容器的指針，專門有一塊內(nèi)存用來存儲列表元素，這塊內(nèi)存的大小就是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)建列表對象需要分配的內(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)建過程大致是：
- 檢查size參數(shù)是否有效，如果小于0，直接返回NULL，創(chuàng)建失敗
- 檢查size參數(shù)是否超出Python所能接受的大小，如果大于PY_SIZE_MAX（64位機器為8字節(jié)，在32位機器為4字節(jié)），內(nèi)存溢出。
- 檢查緩沖池free_list是否有可用的對象，有則直接從緩沖池中使用，沒有則創(chuàng)建新的PyListObject，分配內(nèi)存。
- 初始化ob_item中的元素的值為Null
- 設(shè)置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占用的內(nèi)存，只要緩沖池空間還沒滿，那么就把該PyListObject加入到緩沖池中（此時PyListObject占用的內(nèi)存并不會正真正回收給系統(tǒng)，下次創(chuàng)建PyListObject優(yōu)先從緩沖池中獲取PyListObject），否則釋放PyListObject對象的內(nèi)存空間。
列表元素插入
設(shè)置列表某個位置的值時，如“l(fā)ist[1]=0”，列表的內(nèi)存結(jié)構(gòu)并不會發(fā)生變化，而往列表中插入元素時會改變列表的內(nèi)存結(jié)構(gòu)：
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;
}
相比設(shè)置某個列表位置的值來說，插入操作要多一次PyListObject容量大小的調(diào)整，邏輯是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對象不會重新分配內(nèi)存空間，否則重新分配內(nèi)存空間，如果newsize
總結(jié)
- PyListObject緩沖池的創(chuàng)建發(fā)生在列表銷毀的時候。
- PyListObject對象的創(chuàng)建分兩步：先創(chuàng)建PyListObject對象，然后初始化元素列表為NULL。
- PyListObject對象的銷毀分兩步：先銷毀PyListObject對象中的元素列表，然后銷毀PyListObject本身。
- PyListObject對象內(nèi)存的占用空間會根據(jù)列表長度的變化而調(diào)整。
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
