Python源碼解析之List
更新時(shí)間：2021年05月21日 14:47:59 作者：大兵_xd
今天帶大家來(lái)復(fù)習(xí)Python底層代碼LIST,文中有非常詳細(xì)的介紹及代碼示例,對(duì)正在學(xué)習(xí)python的小伙伴們有很好地幫助,需要的朋友可以參考下
一、列表結(jié)構(gòu)體
創(chuàng)建列表C語(yǔ)言底層的結(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)部將對(duì)象放在鏈表進(jìn)行內(nèi)存管理
Py_ssize_t ob_refcnt; // 引用計(jì)數(shù)器，就是多少變量用了它
PyObject **ob_item; // 指針的指針，存列表的元素
Py_ssize_t ob_size; // 已有元素個(gè)數(shù)
Py_ssize_t allocated; // 列表容量，可容納個(gè)數(shù)
} PyListObject;
c源碼來(lái)自 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
// 緩存機(jī)制
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_COUNT
count_reuse++;
#endif
} else {
op = PyObject_GC_New(PyListObject, &PyList_Type);
if (op == NULL)
return NULL;Py
#ifdef SHOW_ALLOC_COUNT
count_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; // 元素個(gè)數(shù)
op->allocated = size; // 容量
_PyObject_GC_TRACK(op); //放到雙向鏈表進(jìn)行維護(hù)
return (PyObject *) op; //返回列表的指針
}
三、添加元素
list中插入一個(gè)元素時(shí)，擴(kuò)容連續(xù)的內(nèi)存地址（容量），在內(nèi)存創(chuàng)建需要插入的內(nèi)容p，將地址*p放入list的空間中，所以，PyListObject的ob_item是指針的指針
擴(kuò)容的曲線一般就是0，4，8，16，24…
// 添加元素
static int
app1(PyListObject *self, PyObject *v)
{
// 獲取實(shí)際元素個(gè)數(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;
}
// 計(jì)算當(dāng)前容量和內(nèi)部元素個(gè)數(shù)
// 直接添加元素/擴(kuò)容添加
if (list_resize(self, n+1) == -1)
return -1;
// 將元素添加到ob_item，v
Py_INCREF(v);
PyList_SET_ITEM(self, n, v);
return 0;
}
- 擴(kuò)容
// 擴(kuò)容機(jī)制
// newsize: 已存在元素個(gè)數(shù)+1
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated;
Py_ssize_t allocated = self->allocated; // 當(dāng)前的容量
// 1,容量大于個(gè)數(shù)
// 2,個(gè)數(shù)大于容量的一半（容量足夠且沒有內(nèi)存浪費(fè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, ...
*/
// 擴(kuò)容機(jī)制的算法
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;
// 擴(kuò)容/縮容（涉及原來(lái)元素的遷移）
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;
}
// 賦值，更新個(gè)數(shù)和容量
self->ob_item = items;
Py_SIZE(self) = newsize;
self->allocated = new_allocated;
return 0;
}
四、移除元素
list.pop()
刪除最后一個(gè)元素只需要修改size，不需要清除數(shù)據(jù)，下次append可以直接覆蓋這個(gè)位置
指定索引位置移除后，向前補(bǔ)位
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];
// 刪除最后一個(gè)，僅改變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);
// 不是最后一個(gè)，需要移動(dòng)數(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 int
list_clear(PyListObject *a)
{
Py_ssize_t i;
PyObject **item = a->ob_item;
if (item != NULL) {
i = Py_SIZE(a);
// 各個(gè)元素設(shè)置為空
Py_SIZE(a) = 0;
a->ob_item = NULL;
a->allocated = 0;
// 引用計(jì)數(shù)器-1
while (--i >= 0) {
Py_XDECREF(item[i]);
}
PyMem_FREE(item);
}
return 0;
}
六、銷毀
del list
銷毀列表對(duì)象的操作
將列表的引用計(jì)數(shù)-1
引用計(jì)數(shù)>0，還有應(yīng)用的話不做操作
引用計(jì)數(shù)=0，沒人使用
- 處理列表的元素，將所有引用計(jì)數(shù)-1（GC回收0計(jì)數(shù)）
- ob_item=0,ob_size=0,ob_allocated=0
- 將列表從雙向鏈表移除，可以銷毀
- 為了提高效率，Python結(jié)束期在內(nèi)部為free_list緩存80個(gè)list，存放無(wú)使用的list，再創(chuàng)建的時(shí)候直接從緩存中拿來(lái)初始化。如果已經(jīng)存了80個(gè)，del 的時(shí)候直接在內(nèi)存中銷毀對(duì)象
static void
list_dealloc(PyListObject *op)
{
Py_ssize_t i;
// 判斷引用計(jì)數(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個(gè)的話緩存這個(gè)list
if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
free_list[numfree++] = op;
else
Py_TYPE(op)->tp_free((PyObject *)op);
Py_TRASHCAN_SAFE_END(op)
}
就是說(shuō)創(chuàng)建列表時(shí)，實(shí)際上不會(huì)直接開辟內(nèi)存，而是先看看free_list
# 兩次list的地址相同 >>> list1=[1,2,3] >>> id(list1) 69070216L >>> del list1 >>> list2=[0,0,0] >>> id(list2) 69303304L >>>
到此這篇關(guān)于Python源碼解析之List的文章就介紹到這了,更多相關(guān)Python List內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Python設(shè)計(jì)模式行為型責(zé)任鏈模式
這篇文章主要介紹了Python設(shè)計(jì)模式行為型責(zé)任鏈模式，責(zé)任鏈模式將能處理請(qǐng)求的對(duì)象連成一條鏈，并沿著這條鏈傳遞該請(qǐng)求，直到有一個(gè)對(duì)象處理請(qǐng)求為止，避免請(qǐng)求的發(fā)送者和接收者之間的耦合關(guān)系，下圍繞改內(nèi)容介紹具有一點(diǎn)的參考價(jià)值,需要的朋友可以參考下2022-02-02
這篇文章主要介紹了基于python goto的正確用法說(shuō)明，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來(lái)看看吧2021-03-03
這篇文章主要介紹了python通過socket查詢whois的方法,涉及Python基于socket模塊進(jìn)行查詢的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-07-07
python皮爾遜相關(guān)性數(shù)據(jù)分析分析及實(shí)例代碼
這篇文章主要為大家介紹了python皮爾遜相關(guān)性分析及實(shí)例代碼，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-02-02
如何準(zhǔn)確判斷請(qǐng)求是搜索引擎爬蟲（蜘蛛）發(fā)出的請(qǐng)求
我們的網(wǎng)站經(jīng)常被各種蜘蛛爬蟲光顧，由于這些爬蟲都有UserAgent，所以很多朋友使用UserAgent判斷請(qǐng)求的發(fā)起者是否是搜索引擎爬蟲的方式是很不準(zhǔn)確的，接下來(lái)，通過本篇文章給大家介紹準(zhǔn)確判斷請(qǐng)求是搜索引擎爬蟲（蜘蛛）發(fā)出的請(qǐng)求的方法，需要的朋友可以參考下2015-10-10
對(duì)python以16進(jìn)制打印字節(jié)數(shù)組的方法詳解
今天小編就為大家分享一篇對(duì)python以16進(jìn)制打印字節(jié)數(shù)組的方法詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來(lái)看看吧2019-01-01
python利用faker庫(kù)批量生成測(cè)試數(shù)據(jù)
小編經(jīng)常需要批量測(cè)試一些數(shù)據(jù)，有時(shí)候測(cè)試環(huán)境又暫時(shí)沒數(shù)據(jù)，特意找了一下，發(fā)現(xiàn)有一個(gè)可批量生成數(shù)據(jù)的python庫(kù)—-faker,現(xiàn)在就介紹一下它的使用方法，如果你不想一行一行輸入代碼，小編提供了完整測(cè)試代碼，見文末代碼章節(jié)。2020-10-10
這篇文章主要介紹了python 三種方法提取pdf中的圖片，幫助大家更好的理解和使用python，感興趣的朋友可以了解下2021-02-02
這篇文章主要為大家詳細(xì)介紹了Linux下多個(gè)Python版本的安裝教程，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-08-08
java虛擬機(jī)中棧的運(yùn)行知識(shí)點(diǎn)總結(jié)
在本篇文章里小編給大家整理的是一篇關(guān)于java虛擬機(jī)中棧的運(yùn)行知識(shí)點(diǎn)總結(jié)，有需要的朋友們可以學(xué)習(xí)參考下。2021-06-06