Python源碼解析之List
創建列表C語言底層的結構體
lists = []list.append(’name’)list.append(’age’)list.append(’grade’)
typedef struct{struct _object *_ob_next;struct _object *_ob_prev; // python內部將對象放在鏈表進行內存管理Py_ssize_t ob_refcnt;// 引用計數器，就是多少變量用了它PyObject **ob_item;// 指針的指針，存列表的元素Py_ssize_t ob_size;// 已有元素個數Py_ssize_t allocated;// 列表容量，可容納個數} PyListObject;
c源碼來自 listobject.c
二、創建列表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; // 元素個數 op->allocated = size; // 容量 _PyObject_GC_TRACK(op); //放到雙向鏈表進行維護 return (PyObject *) op; //返回列表的指針}三、添加元素
list中插入一個元素時，擴容連續的內存地址（容量），在內存創建需要插入的內容p，將地址*p放入list的空間中，所以，PyListObject的ob_item是指針的指針
擴容的曲線一般就是0，4，8，16，24…
// 添加元素static intapp1(PyListObject *self, PyObject *v){ // 獲取實際元素個數 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; } // 計算當前容量和內部元素個數 // 直接添加元素/擴容添加 if (list_resize(self, n+1) == -1)return -1; // 將元素添加到ob_item，v Py_INCREF(v); PyList_SET_ITEM(self, n, v); return 0;} 擴容
// 擴容機制 // newsize: 已存在元素個數+1static intlist_resize(PyListObject *self, Py_ssize_t newsize){ PyObject **items; size_t new_allocated; Py_ssize_t allocated = self->allocated; // 當前的容量 // 1,容量大于個數 // 2,個數大于容量的一半（容量足夠且沒有內存浪費） 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; } // 賦值，更新個數和容量 self->ob_item = items; Py_SIZE(self) = newsize; self->allocated = new_allocated; return 0;}四、移除元素
list.pop()刪除最后一個元素只需要修改size，不需要清除數據，下次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); // 不是最后一個，需要移動數據位置 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;// 引用計數器-1while (--i >= 0) { Py_XDECREF(item[i]);}PyMem_FREE(item); } return 0;}六、銷毀
del list
銷毀列表對象的操作將列表的引用計數-1引用計數>0，還有應用的話不做操作引用計數=0，沒人使用
處理列表的元素，將所有引用計數-1（GC回收0計數） ob_item=0,ob_size=0,ob_allocated=0 將列表從雙向鏈表移除，可以銷毀 為了提高效率，Python結束期在內部為free_list緩存80個list，存放無使用的list，再創建的時候直接從緩存中拿來初始化。如果已經存了80個，del 的時候直接在內存中銷毀對象static voidlist_dealloc(PyListObject *op){ Py_ssize_t i; // 判斷引用計數是否為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)}
就是說創建列表時，實際上不會直接開辟內存，而是先看看free_list
# 兩次list的地址相同>>> list1=[1,2,3]>>> id(list1)69070216L>>> del list1>>> list2=[0,0,0]>>> id(list2)69303304L>>>
到此這篇關于Python源碼解析之List的文章就介紹到這了,更多相關Python List內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網！
相關文章：
網公網安備