溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“Python虛擬機中列表的實現原理是什么”，在日常操作中，相信很多人在Python虛擬機中列表的實現原理是什么問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Python虛擬機中列表的實現原理是什么”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！
在 cpython 實現的 python 虛擬機當中，下面就是 cpython 內部列表實現的源代碼：
typedef struct {
PyObject_VAR_HEAD
/* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
PyObject **ob_item;
/* ob_item contains space for 'allocated' elements. The number
* currently in use is ob_size.
* Invariants:
* 0 <= ob_size <= allocated
* len(list) == ob_size
* ob_item == NULL implies ob_size == allocated == 0
* list.sort() temporarily sets allocated to -1 to detect mutations.
*
* Items must normally not be NULL, except during construction when
* the list is not yet visible outside the function that builds it.
*/
Py_ssize_t allocated;
} PyListObject;
#define PyObject_VAR_HEAD PyVarObject ob_base;
typedef struct {
PyObject ob_base;
Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;
typedef struct _object {
_PyObject_HEAD_EXTRA // 這個宏定義為空
Py_ssize_t ob_refcnt;
struct _typeobject *ob_type;
} PyObject;將上面的結構體展開之后，PyListObject 的結構大致如下所示：
現在來解釋一下上面的各個字段的含義：
Py_ssize_t，一個整型數據類型。
ob_refcnt，表示對象的引用記數的個數，這個對于垃圾回收很有用處，后面我們分析虛擬機中垃圾回收部分在深入分析。
ob_type，表示這個對象的數據類型是什么，在 python 當中有時候需要對數據的數據類型進行判斷比如 isinstance, type 這兩個關鍵字就會使用到這個字段。
ob_size，這個字段表示這個列表當中有多少個元素。
ob_item，這是一個指針，指向真正保存 python 對象數據的地址，大致的內存他們之間大致的內存布局如下所示：
allocated，這個表示在進行內存分配的時候，一共分配了多少個 (PyObject *) ，真實分配的內存空間為 allocated * sizeof(PyObject *)。
首先需要了解的是在 python 虛擬機內部為列表創建了一個數組，所有的創建的被釋放的內存空間，并不會直接進行釋放而是會將這些內存空間的首地址保存到這個數組當中，好讓下一次申請創建新的列表的時候不需要再申請內存空間，而是直接將之前需要釋放的內存直接進行復用即可。
/* Empty list reuse scheme to save calls to malloc and free */ #ifndef PyList_MAXFREELIST #define PyList_MAXFREELIST 80 #endif static PyListObject *free_list[PyList_MAXFREELIST]; static int numfree = 0;
free_list，保存被釋放的內存空間的首地址。
numfree，目前 free_list 當中有多少個地址是可以被使用的，事實上是 free_list 前 numfree 個首地址是可以被使用的。
創建鏈表的代碼如下所示（為了精簡刪除了一些代碼只保留核心部分）：
PyObject *
PyList_New(Py_ssize_t size)
{
PyListObject *op;
size_t nbytes;
/* 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 *);
// 如果 numfree 不等于 0 那么說明現在 free_list 有之前使用被釋放的內存空間直接使用這部分即可
if (numfree) {
numfree--;
op = free_list[numfree]; // 將對應的首地址返回
_Py_NewReference((PyObject *)op); // 這條語句的含義是將 op 這個對象的 reference count 設置成 1
} else {
// 如果沒有空閑的內存空間 那么就需要申請內存空間 這個函數也會對對象的 reference count 進行初始化 設置成 1
op = PyObject_GC_New(PyListObject, &PyList_Type);
if (op == NULL)
return NULL;
}
/* 下面是申請列表對象當中的 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();
}
// 對元素進行初始化操作 全部賦值成 0
memset(op->ob_item, 0, nbytes);
}
// Py_SIZE 是一個宏
Py_SIZE(op) = size; // 這條語句會被展開成 (PyVarObject*)(ob))->ob_size = size
// 分配數組的元素個數是 size
op->allocated = size;
// 下面這條語句對于垃圾回收比較重要 主要作用就是將這個列表對象加入到垃圾回收的鏈表當中
// 后面如果這個對象的 reference count 變成 0 或者其他情況 就可以進行垃圾回收了
_PyObject_GC_TRACK(op);
return (PyObject *) op;
}在 cpython 當中，創建鏈表的字節碼為 BUILD_LIST，我們可以在文件 ceval.c 當中找到對應的字節碼對應的執行步驟：
TARGET(BUILD_LIST) {
PyObject *list = PyList_New(oparg);
if (list == NULL)
goto error;
while (--oparg >= 0) {
PyObject *item = POP();
PyList_SET_ITEM(list, oparg, item);
}
PUSH(list);
DISPATCH();
}從上面 BUILD_LIST 字節碼對應的解釋步驟可以知道，在解釋執行字節碼 BUILD_LIST 的時候確實調用了函數 PyList_New 創建一個新的列表。
static PyObject *
// 這個函數的傳入參數是列表本身 self 需要 append 的元素為 v
// 也就是將對象 v 加入到列表 self 當中
listappend(PyListObject *self, PyObject *v)
{
if (app1(self, v) == 0)
Py_RETURN_NONE;
return NULL;
}
static int
app1(PyListObject *self, PyObject *v)
{
// PyList_GET_SIZE(self) 展開之后為 ((PyVarObject*)(self))->ob_size
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;
}
// 下面的函數 list_resize 會保存 ob_item 指向的位置能夠容納最少 n+1 個元素（PyObject *）
// 如果容量不夠就會進行擴容操作
if (list_resize(self, n+1) == -1)
return -1;
// 將對象 v 的 reference count 加一 因為列表當中使用了一次這個對象 所以對象的引用計數需要進行加一操作
Py_INCREF(v);
PyList_SET_ITEM(self, n, v); // 宏展開之后 ((PyListObject *)(op))->ob_item[i] = v
return 0;
}static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated;
Py_ssize_t allocated = self->allocated;
/* Bypass realloc() when a previous overallocation is large enough
to accommodate the newsize. If the newsize falls lower than half
the allocated size, then proceed with the realloc() to shrink the list.
*/
// 如果列表已經分配的元素個數大于需求個數 newsize 的就直接返回不需要進行擴容
if (allocated >= newsize && newsize >= (allocated >> 1)) {
assert(self->ob_item != NULL || newsize == 0);
Py_SIZE(self) = newsize;
return 0;
}
/* This over-allocates proportional to the list size, making room
* for additional growth. The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
// 這是核心的數組大小擴容機制 new_allocated 表示新增的數組大小
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 這是一個宏定義 會申請 new_allocated 個數元素并且將原來數組的元素拷貝到新的數組當中
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;
}在上面的擴容機制下，數組的大小變化大致如下所示：
newsize≈size⋅(size+1)1/8
在列表當中插入一個數據比較簡單，只需要將插入位置和其后面的元素往后移動一個位置即可，整個過程如下所示：
在 cpython 當中列表的插入函數的實現如下所示：
參數 op 表示往哪個鏈表當中插入元素。
參數 where 表示在鏈表的哪個位置插入元素。
參數 newitem 表示新插入的元素。
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);
}
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;
}
// 確保列表能夠容納 n + 1 個元素
if (list_resize(self, n+1) == -1)
return -1;
// 這里是 python 的一個小 trick 就是下標能夠有負數的原理
if (where < 0) {
where += n;
if (where < 0)
where = 0;
}
if (where > n)
where = n;
items = self->ob_item;
// 從后往前進行元素的拷貝操作，也就是將插入位置及其之后的元素往后移動一個位置
for (i = n; --i >= where; )
items[i+1] = items[i];
// 因為鏈表應用的對象，因此對象的 reference count 需要進行加一操作
Py_INCREF(v);
// 在列表當中保存對象 v
items[where] = v;
return 0;
}對于數組 ob_item 來說，刪除一個元素就需要將這個元素后面的元素往前移動，因此整個過程如下所示：
static PyObject *
listremove(PyListObject *self, PyObject *v)
{
Py_ssize_t i;
// 編譯數組 ob_item 查找和對象 v 相等的元素并且將其刪除
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;
}
// 如果沒有找到這個元素就進行報錯處理 在下面有一個例子重新編譯 python 解釋器 將這個錯誤內容修改的例子
PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
return NULL;
}執行的 python 程序內容為：
data = [] data.remove(1)
下面是整個修改內容和報錯結果：
從上面的結果我們可以看到的是，我們修改的錯誤信息正確打印了出來。
這個函數的主要作用就是統計列表 self 當中有多少個元素和 v 相等。
static PyObject *
listcount(PyListObject *self, PyObject *v)
{
Py_ssize_t count = 0;
Py_ssize_t i;
for (i = 0; i < Py_SIZE(self); i++) {
int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
// 如果相等則將 count 進行加一操作
if (cmp > 0)
count++;
// 如果出現錯誤就返回 NULL
else if (cmp < 0)
return NULL;
}
// 將一個 Py_ssize_t 的變量變成 python 當中的對象
return PyLong_FromSsize_t(count);
}這是列表的淺拷貝函數，它只拷貝了真實 python 對象的指針，并沒有拷貝真實的 python 對象 ，從下面的代碼可以知道列表的拷貝是淺拷貝，當 b 對列表當中的元素進行修改時，列表 a 當中的元素也改變了。如果需要進行深拷貝可以使用 copy 模塊當中的 deepcopy 函數。
>>> a = [1, 2, [3, 4]] >>> b = a.copy() >>> b[2][1] = 5 >>> b [1, 2, [3, 5]]
copy 函數對應的源代碼（listcopy）如下所示：
static PyObject *
listcopy(PyListObject *self)
{
return list_slice(self, 0, Py_SIZE(self));
}
static PyObject *
list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
// Py_SIZE(a) 返回列表 a 當中元素的個數（注意不是數組的長度 allocated）
PyListObject *np;
PyObject **src, **dest;
Py_ssize_t i, len;
if (ilow < 0)
ilow = 0;
else if (ilow > Py_SIZE(a))
ilow = Py_SIZE(a);
if (ihigh < ilow)
ihigh = ilow;
else if (ihigh > Py_SIZE(a))
ihigh = Py_SIZE(a);
len = ihigh - ilow;
np = (PyListObject *) PyList_New(len);
if (np == NULL)
return NULL;
src = a->ob_item + ilow;
dest = np->ob_item;
// 可以看到這里循環拷貝的是指向真實 python 對象的指針 并不是真實的對象
for (i = 0; i < len; i++) {
PyObject *v = src[i];
// 同樣的因為并沒有創建新的對象，但是這個對象被新的列表使用到啦 因此他的 reference count 需要進行加一操作 Py_INCREF(v) 的作用：將對象 v 的 reference count 加一
Py_INCREF(v);
dest[i] = v;
}
return (PyObject *)np;
}下圖就是使用 a.copy() 淺拷貝的時候，內存的布局的示意圖，可以看到列表指向的對象數組發生了變化，但是數組中元素指向的 python 對象并沒有發生變化。
下面是對列表對象進行深拷貝的時候內存的大致示意圖，可以看到數組指向的 python 對象也是不一樣的。
當我們在使用 list.clear() 的時候會調用下面這個函數。清空列表需要注意的就是將表示列表當中元素個數的 ob_size 字段設置成 0 ，同時將列表當中所有的對象的 reference count 設置進行 -1 操作，這個操作是通過宏 Py_XDECREF 實現的，這個宏還會做另外一件事就是如果這個對象的引用計數變成 0 了，那么就會直接釋放他的內存。
static PyObject *
listclear(PyListObject *self)
{
list_clear(self);
Py_RETURN_NONE;
}
static int
list_clear(PyListObject *a)
{
Py_ssize_t i;
PyObject **item = a->ob_item;
if (item != NULL) {
/* Because XDECREF can recursively invoke operations on
this list, we make it empty first. */
i = Py_SIZE(a);
Py_SIZE(a) = 0;
a->ob_item = NULL;
a->allocated = 0;
while (--i >= 0) {
Py_XDECREF(item[i]);
}
PyMem_FREE(item);
}
/* Never fails; the return value can be ignored.
Note that there is no guarantee that the list is actually empty
at this point, because XDECREF may have populated it again! */
return 0;
}在 python 當中如果我們想要反轉類表當中的內容的話，就會使用這個函數 reverse 。
>>> a = [i for i in range(10)] >>> a.reverse() >>> a [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
其對應的源程序如下所示：
static PyObject *
listreverse(PyListObject *self)
{
if (Py_SIZE(self) > 1)
reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
Py_RETURN_NONE;
}
static void
reverse_slice(PyObject **lo, PyObject **hi)
{
assert(lo && hi);
--hi;
while (lo < hi) {
PyObject *t = *lo;
*lo = *hi;
*hi = t;
++lo;
--hi;
}
}上面的源程序還是比較容易理解的，給 reverse_slice 傳遞的參數就是保存數據的數組的首尾地址，然后不斷的將首尾數據進行交換（其實是交換指針指向的地址）。
到此，關于“Python虛擬機中列表的實現原理是什么”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
