python中 list的實(shí)現(xiàn)
python中的LIST非常強(qiáng)大,它既有數(shù)組的下標(biāo)查詢優(yōu)勢(shì),
又有鏈表這樣動(dòng)態(tài)增減的高速率;
列表對(duì)象的C語言結(jié)構(gòu)體:
typedef struct {
int ob_refcnt; # 列表對(duì)象引用計(jì)數(shù)
struct _typeobject *ob_type; # 列表類型對(duì)象
int ob_size; # 列表元素的長度
//這三個(gè)也可以用一個(gè)結(jié)構(gòu)體 PyObject_VAR_HEAD 來代替
PyObject **ob_item; # 真正存放列表元素容器的指針流炕，list[0] 就是 ob_item[0]
Py_ssize_t allocated; # 當(dāng)前列表可容納的元素大小
} PyListObject;
滿足條件:
- 0 <= ob_size <= allocated
- len(list) == ob_size
- ob_item == NULL 時(shí) ob_size == allocated == 0
ref_count,ob_size,allocated, ob_item -> list[]
列表對(duì)象的創(chuàng)建:
// 列表緩沖池, 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;
}
//如果size小于0 直接返回NULL,創(chuàng)建失敗
/* 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();
//如果size超過了python 能接受的大小,內(nèi)存溢出
nbytes = size * sizeof(PyObject *);
//獲取所需內(nèi)存大小
if (numfree) {
numfree--;
op = free_list[numfree];
_Py_NewReference((PyObject *)op);
//如果緩沖區(qū)有內(nèi)存,先拿緩沖區(qū)的內(nèi)存
} else {
op = PyObject_GC_New(PyListObject, &PyList_Type);
if (op == NULL)
return NULL;
//不然就申請(qǐng)新的內(nèi)存
}
如果申請(qǐng)一個(gè)空的列表,下一項(xiàng)就為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位機(jī)器為8字節(jié)，在32位機(jī)器為4字節(jié)），內(nèi)存溢出抚垃。
- 檢查緩沖池free_list是否有可用的對(duì)象，有則直接從緩沖池中使用趟大，沒有則創(chuàng)建新的PyListObject鹤树，分配內(nèi)存。
- 初始化ob_item中的元素的值為Null
- 設(shè)置PyListObject的allocated和ob_size逊朽。
list_dealloc函數(shù),用來銷毀列表返回內(nèi)存給緩沖池:
static void
list_dealloc(PyListObject *op)
{
Py_ssize_t i;
PyObject_GC_UnTrack(op);//拆包檢查
Py_TRASHCAN_SAFE_BEGIN(op)
if (op->ob_item != NULL) {
//如果不是空的列表
i = Py_SIZE(op);//獲取列表長度
while (--i >= 0) {
Py_XDECREF(op->ob_item[i]);//列表中所有元素的引用計(jì)數(shù)減一
}
PyMem_FREE(op->ob_item);//釋放ob_item的內(nèi)存
}
if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
free_list[numfree++] = op;
//如果當(dāng)前緩沖區(qū)還有位置,將op直接放到緩沖區(qū),免得重復(fù)申請(qǐng)新內(nèi)存來new 一個(gè)List (為什么能直接歸還,因?yàn)槊總€(gè)listobject不同的地方在于ob-item ,其他屬性可以在從緩沖區(qū)拿出來的時(shí)候賦值變化,避免了多次malloc)
//（此時(shí)PyListObject占用的內(nèi)存并不會(huì)正真正回收給系統(tǒng)罕伯，下次創(chuàng)建PyListObject優(yōu)先從緩沖池中獲取PyListObject）
else
Py_TYPE(op)->tp_free((PyObject *)op);//沒有就直接歸還整個(gè)結(jié)構(gòu)體的內(nèi)存
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)存空間。
查看列表的某個(gè)下標(biāo)元素值的時(shí)候:
PyObject *
PyList_GetItem(PyObject *op, Py_ssize_t i)
{
if (!PyList_Check(op)) {
PyErr_BadInternalCall();
return NULL;
}
if (i < 0 || i >= Py_SIZE(op)) {
if (indexerr == NULL) {
indexerr = PyString_FromString(
"list index out of range");
if (indexerr == NULL)
return NULL;
}
PyErr_SetObject(PyExc_IndexError, indexerr);
return NULL;
}
return ((PyListObject *)op) -> ob_item[i];
}
直接檢查是否越界,沒越界直接返回ob_item[i]所在元素,跟普通數(shù)組類似
list 位置調(diào)整,這段代碼解釋了Python 動(dòng)態(tài)調(diào)整的原理
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated;
Py_ssize_t allocated = self->allocated;
//當(dāng) newsize 位于當(dāng)前大小的一半以上時(shí)候,將list大小變?yōu)閚ewsize
if (allocated >= newsize && newsize >= (allocated >> 1)) {
assert(self->ob_item != NULL || newsize == 0);
Py_SIZE(self) = newsize;
return 0;
}
//需要增大列表的時(shí)候,這與列表大小成比例地分配涤妒，
//創(chuàng)造空間進(jìn)一步增長单雾。 過度分配是溫和的.
//新增的長度 趨勢(shì)是 0,4,8,16,25,35,46
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;
}
list_resize() 函數(shù)。它會(huì)多申請(qǐng)一些內(nèi)存她紫，避免頻繁調(diào)用 list_resize() 函數(shù)铁坎。列表的增長模式為：0，4犁苏，8硬萍，16，25围详，35朴乖，46祖屏，58，72买羞，88
插入:
static int
app1(PyListObject *self, PyObject *v)
{
Py_ssize_t n = PyList_GET_SIZE(self);//獲取list 大小
assert (v != NULL);
if (n == PY_SSIZE_T_MAX) {
PyErr_SetString(PyExc_OverflowError,
"cannot add more objects to list");
return -1;
}//如果超過List 長度,則報(bào)錯(cuò)
if (list_resize(self, n+1) == -1)
return -1;
//調(diào)整list大小,增添一個(gè)空間的(實(shí)際上是得到4個(gè)新增空間)
// new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
//new_allocated+=newsize
Py_INCREF(v);
PyList_SET_ITEM(self, n, v);
return 0;
//增加引用,加一
}
append 方法 實(shí)現(xiàn)
int
PyList_Append(PyObject *op, PyObject *newitem)
{
//引用app1 然后將元素添加到最后一位
if (PyList_Check(op) && (newitem != NULL))
return app1((PyListObject *)op, newitem);
PyErr_BadInternalCall();
return -1;
}
現(xiàn)在分配了 4 個(gè)用來裝列表元素的槽空間袁勺，并且第一個(gè)空間中為整數(shù) 1。如下圖顯示 l[0] 指向我們新添加的整數(shù)對(duì)象畜普。虛線的方框表示已經(jīng)分配但沒有使用的槽空間期丰。
列表追加元素操作的平均復(fù)雜度為 O(1)。
image.png
繼續(xù)添加新的元素：l.append(2)吃挑。調(diào)用 list_resize 函數(shù)钝荡，參數(shù)為 n+1 = 2， 但是因?yàn)橐呀?jīng)申請(qǐng)了 4 個(gè)槽空間舶衬，所以不需要再申請(qǐng)內(nèi)存空間埠通。再添加兩個(gè)整數(shù)的情況也是一樣的：l.append(3)，l.append(4)逛犹。下圖顯示了我們現(xiàn)在的情況:
image.png
插入算法:
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
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;
//增加一個(gè)位置
if (where < 0) {
where += n;
//如果是倒數(shù)的位置,直接加長度
if (where < 0)
where = 0;
}
//如果加上長度都小于0 ,證明越界了 只能變0
if (where > n)
where = n;
//如果是插入位置越界,只能放在最后,確定插入位置
items = self->ob_item;
for (i = n; --i >= where; )
items[i+1] = items[i];
//復(fù)制列表的元素
Py_INCREF(v);
items[where] = v;
return 0;
}
int
PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
{
if (!PyList_Check(op)) {
PyErr_BadInternalCall();
return -1;
}
return ins1((PyListObject *)op, where, newitem);
}
插入是 ,,先確定插入位置,再新建列表保存之前的元素,新加插入元素到新的列表:
- resize n+1
- 確定插入點(diǎn)
- 插入點(diǎn)后所有元素后移
- 執(zhí)行插入
remove 函數(shù)
static PyObject *
listremove(PyListObject *self, PyObject *v)
{
Py_ssize_t i;
for (i = 0; i < Py_SIZE(self); i++) {
int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
if (cmp > 0) {
if (list_ass_slice(self, i, i+1,
(PyObject *)NULL) == 0)
Py_RETURN_NONE;
return NULL;
}
else if (cmp < 0)
return NULL;
}
PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
return NULL;
}
為了做列表的切片并且刪除元素端辱，調(diào)用了 list_ass_slice() 函數(shù)，
- 找到要?jiǎng)h除元素位置
- 刪除之, 后面元素前移
Py_INCREF(pyObject *o) 增加該變量的引用
