目錄一、列表結(jié)構(gòu)體二、創(chuàng)建列表三、添加元素四、移除元素五、清空六、銷毀一、列表結(jié)構(gòu)體

創(chuàng)建列表C語言底層的結(jié)構(gòu)體

lists = []list.append(’name’)list.append(’age’)list.append(’grade’)

typedef struct{struct _object *_ob_next;struct _object *_ob_prev; // python內(nèi)部將對象放在鏈表進行內(nèi)存管理Py_ssize_t ob_refcnt;// 引用計數(shù)器，就是多少變量用了它PyObject **ob_item;// 指針的指針，存列表的元素Py_ssize_t ob_size;// 已有元素個數(shù)Py_ssize_t allocated;// 列表容量，可容納個數(shù)} PyListObject;

c源碼來自 listobject.c

二、創(chuàng)建列表

name_list = [ ]

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 // 緩存機制 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);#ifdef SHOW_ALLOC_COUNTcount_reuse++;#endif } else {op = PyObject_GC_New(PyListObject, &PyList_Type);if (op == NULL) return NULL;Py#ifdef SHOW_ALLOC_COUNTcount_alloc++;#endif } 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); } Py_SIZE(op) = size; // 元素個數(shù) op->allocated = size; // 容量 _PyObject_GC_TRACK(op); //放到雙向鏈表進行維護 return (PyObject *) op; //返回列表的指針}三、添加元素

list中插入一個元素時，擴容連續(xù)的內(nèi)存地址（容量），在內(nèi)存創(chuàng)建需要插入的內(nèi)容p，將地址*p放入list的空間中，所以，PyListObject的ob_item是指針的指針

擴容的曲線一般就是0，4，8，16，24…

// 添加元素static intapp1(PyListObject *self, PyObject *v){ // 獲取實際元素個數(shù) Py_ssize_t n = PyList_GET_SIZE(self); assert (v != NULL); if (n == PY_SSIZE_T_MAX) {PyErr_SetString(PyExc_OverflowError, 'cannot add more objects to list');return -1; } // 計算當前容量和內(nèi)部元素個數(shù) // 直接添加元素/擴容添加 if (list_resize(self, n+1) == -1)return -1; // 將元素添加到ob_item，v Py_INCREF(v); PyList_SET_ITEM(self, n, v); return 0;} 擴容

// 擴容機制 // newsize: 已存在元素個數(shù)+1static intlist_resize(PyListObject *self, Py_ssize_t newsize){ PyObject **items; size_t new_allocated; Py_ssize_t allocated = self->allocated; // 當前的容量 // 1,容量大于個數(shù) // 2,個數(shù)大于容量的一半（容量足夠且沒有內(nèi)存浪費） if (allocated >= newsize && newsize >= (allocated >> 1)) {assert(self->ob_item != NULL || newsize == 0);Py_SIZE(self) = newsize;return 0; } /* * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... */ // 擴容機制的算法 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); elseitems = NULL; if (items == NULL) {PyErr_NoMemory();return -1; } // 賦值，更新個數(shù)和容量 self->ob_item = items; Py_SIZE(self) = newsize; self->allocated = new_allocated; return 0;}四、移除元素

list.pop()刪除最后一個元素只需要修改size，不需要清除數(shù)據(jù)，下次append可以直接覆蓋這個位置指定索引位置移除后，向前補位

static PyObject *listpop(PyListObject *self, PyObject *args){ Py_ssize_t i = -1; PyObject *v; int status; if (!PyArg_ParseTuple(args, '|n:pop', &i))return NULL; if (Py_SIZE(self) == 0) {/* Special-case most common failure cause */PyErr_SetString(PyExc_IndexError, 'pop from empty list');return NULL; } if (i < 0)i += Py_SIZE(self); if (i < 0 || i >= Py_SIZE(self)) {PyErr_SetString(PyExc_IndexError, 'pop index out of range');return NULL; } v = self->ob_item[i]; // 刪除最后一個，僅改變size if (i == Py_SIZE(self) - 1) {status = list_resize(self, Py_SIZE(self) - 1);assert(status >= 0);return v; /* and v now owns the reference the list had */ } Py_INCREF(v); // 不是最后一個，需要移動數(shù)據(jù)位置 status = list_ass_slice(self, i, i+1, (PyObject *)NULL); assert(status >= 0); /* Use status, so that in a release build compilers don’t * complain about the unused name. */ (void) status; return v;}五、清空

list.clear()

static intlist_clear(PyListObject *a){ Py_ssize_t i; PyObject **item = a->ob_item; if (item != NULL) {i = Py_SIZE(a);// 各個元素設置為空Py_SIZE(a) = 0;a->ob_item = NULL;a->allocated = 0;// 引用計數(shù)器-1while (--i >= 0) { Py_XDECREF(item[i]);}PyMem_FREE(item); } return 0;}六、銷毀

del list

銷毀列表對象的操作將列表的引用計數(shù)-1引用計數(shù)>0，還有應用的話不做操作引用計數(shù)=0，沒人使用

處理列表的元素，將所有引用計數(shù)-1（GC回收0計數(shù)） ob_item=0,ob_size=0,ob_allocated=0 將列表從雙向鏈表移除，可以銷毀 為了提高效率，Python結(jié)束期在內(nèi)部為free_list緩存80個list，存放無使用的list，再創(chuàng)建的時候直接從緩存中拿來初始化。如果已經(jīng)存了80個，del 的時候直接在內(nèi)存中銷毀對象

static voidlist_dealloc(PyListObject *op){ Py_ssize_t i; // 判斷引用計數(shù)是否為0 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]);}PyMem_FREE(op->ob_item); } // free_list沒有80個的話緩存這個list if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))free_list[numfree++] = op; elsePy_TYPE(op)->tp_free((PyObject *)op); Py_TRASHCAN_SAFE_END(op)}

就是說創(chuàng)建列表時，實際上不會直接開辟內(nèi)存，而是先看看free_list

# 兩次list的地址相同>>> list1=[1,2,3]>>> id(list1)69070216L>>> del list1>>> list2=[0,0,0]>>> id(list2)69303304L>>>

到此這篇關于Python源碼解析之List的文章就介紹到這了,更多相關Python List內(nèi)容請搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持好吧啦網(wǎng)！