知識星球
來源：Python開發者
ID：PythonCoder
原始碼位置 Include/listobject.h | Objects/listobject.c
定義
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
說明
1. PyObject_VAR_HEAD
PyListObject是變長物件
2. PyObject **ob_item;
指向串列元素的指標陣列, list[0] 即 ob_item[0]
3. Py_ssize_t allocated;
allocated串列分配的空間, ob_size為已使用的空間
allocated 總的申請到的記憶體數量
ob_size 實際使用記憶體數量
等式:
0
結構
構造
只有一個方法
定義如下
PyObject *
PyList_New(Py_ssize_t size)
{
PyListObject *op;
size_t nbytes;
#ifdef SHOW_ALLOC_COUNT
static int initialized = 0;
if (!initialized) {
Py_AtExit(show_alloc);
initialized = 1;
}
#endif
// 大小為負數, return
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();
// 計算需要的位元組數(PyObject指標陣列)
nbytes = size * sizeof(PyObject *);
// 如果緩衝池非空, 從緩衝池取
if (numfree) {
// 取緩衝池陣列最後一個物件
numfree—;
op = free_list[numfree];
// set refcnt=1
_Py_NewReference((PyObject *)op);
#ifdef SHOW_ALLOC_COUNT
count_reuse++;
#endif
} else {
// 否則, GC_New分配記憶體空間
op = PyObject_GC_New(PyListObject, &PyList_Type);
// 分配失敗
if (op == NULL)
return NULL;
#ifdef SHOW_ALLOC_COUNT
count_alloc++;
#endif
}
// 確定ob_item串列元素指標的值
// 若大小
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 = size
Py_SIZE(op) = size;
// allocated
op->allocated = size;
// gc用
_PyObject_GC_TRACK(op);
return (PyObject *) op;
}
簡化步驟
1. 判斷串列緩衝池是否為空, 是的話從緩衝池取(復用)
2. 否則, 從記憶體中分配空間
3. 然後初始化資料
結論
Py_SIZE(op) = size;
op->allocated = size;
第一次生成list, 其allocated = ob_size
list_resize
同時註意list_resize方法
extends方法, list_resize(self, m + n)
pop方法, list_resize(self, Py_SIZE(self) – 1)
append方法, list_resize(self, n+1)
其定義
list_resize(PyListObject *self, Py_ssize_t newsize)
{
………..
// 如果 allocated/2 <= newsize <= allocated
// 直接修改ob_size
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);
new_allocated += newsize;
………….
Py_SIZE(self) = newsize;
self->allocated = new_allocated;
}
即
if allocated/2 <= newsize <= allocated
allocated 不變
ob_size = newsize
else
allocated = newsize + ((newsize >> 3) + (newsize < 9 ? 3 : 6))
ob_size = newsize
回收和PyListObject物件緩衝池
看下緩衝池相關的定義
/* Empty list reuse scheme to save calls to malloc and free */
#ifndef PyList_MAXFREELIST
#define PyList_MAXFREELIST 80
#endif
// 80個
static PyListObject *free_list[PyList_MAXFREELIST];
static int numfree = 0;
我們先看下list_dealloc的定義
static void
list_dealloc(PyListObject *op)
{
Py_ssize_t i;
PyObject_GC_UnTrack(op);
Py_TRASHCAN_SAFE_BEGIN(op)
// 遍歷ob_item, 釋放所有類表內元素空間
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);
}
// 如果free_list還沒滿, PyListObject加入到串列中
if (numfree tp_free((PyObject *)op);
Py_TRASHCAN_SAFE_END(op)
}
即
對一個串列物件PyListObject, 回收時, ob_item會被回收, 其每個元素指向的物件取用–1.
但是PyListObject物件本身, 如果緩衝池未滿, 會被放入緩衝池, 復用
緩衝池結構
List的操作過程
插入
1. resize n+1
2. 確定插入點
3. 插入點後所有元素後移
4. 執行插入
示例
>>> a = [1, 2, 3]
>>> a.insert(0, 9)
>>> a
[9, 1, 2, 3]
append
1. resize n+1
2. 放入最後一個位置(ob_size)
示例
>>> a = [1, 2, 3]
>>> a.append(4)
>>> a
[1, 2, 3, 4]
extend
1. 計算兩個list大小 m n
2. resize m+n(此時本身被覆制)
3. 遍歷長度為n的陣列, 從ob_item+m的位置開始加入
示例
>>> m = [1, 2, 3]
>>> n = [4, 5]
>>> m.extend(n)
>>> m
[1, 2, 3, 4, 5]
刪除
1. 找到要刪除元素位置
2. 刪除之, 後面元素前移
示例
>>> a = [1, 2, 3, 2]
>>> a.remove(2)
>>> a
[1, 3, 2]
來源：伯樂線上 – wklken
《Python人工智慧和全棧開發》2018年07月23日即將在北京開課，120天衝擊Python年薪30萬，改變速約~~~~
*宣告：推送內容及圖片來源於網路，部分內容會有所改動，版權歸原作者所有，如來源資訊有誤或侵犯權益，請聯絡我們刪除或授權事宜。
– END –
更多Python好文請點選【閱讀原文】哦
↓↓↓
