深度解密 Python 列表的實現原理

楔子

最近有讀者發了一條私信，希望我介紹一下 Python 列表和字典在讀寫數據的時候誰更快。

那就安排一下，我們先來介紹列表和字典的底層實現，如果瞭解了具體的實現，那麼一切問題就都迎刃而解了。我準備分多篇文章介紹，本次先來介紹列表。

列表是怎麼實現的？

在初學列表的時候，可能書上會告訴你列表就是一個大倉庫，什麼都可以存放。但我們要知道，無論是 Python 的變量，還是列表、元組裏面的元素，它們本質上都是一個指針。

並且根據我們使用列表的經驗，可以得出以下兩個結論：

• 每個列表的元素個數可以不一樣，所以這是一個變長對象；

• 可以對列表的元素進行添加、刪除、修改等操作，所以這是一個可變對象；

而列表在底層由 PyListObject 結構體表示，定義於頭文件 Include/listobject.h 中：

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

我們看到裏面有如下成員：

• PyObject_VAR_HEAD：變長對象的公共頭部信息，包含了以下三個字段；

• ob_refcnt：對象的引用計數；

• ob_type：對象的類型；

• ob_size：負責維護變長對象的長度，比如 len(列表) 的時候，會直接返回這裏的 ob_size；

• ob_item：一個二級指針，指向 PyObject * 類型的指針數組，這個指針數組保存的便是對象的指針，而操作底層數組都是通過 ob_item 來進行操作的；

• allocated：容量，我們知道列表底層是使用了 C 的數組，而底層數組的長度就是列表的容量；

列表之所以要有容量的概念，是因爲列表可以動態添加和刪除元素，但是底層的數組在創建完畢之後，其長度卻是固定的。所以一旦添加新元素的時候，發現數組已滿，這時候只能申請一個更長的數組，同時把舊數組中的元素依次拷貝到新數組裏面（這一過程就是列表的擴容），然後再將新元素添加進去，最後再將舊數組釋放掉。

但是問題來了，總不可能每添加一個元素，就申請一次數組、將所有元素都拷貝一次吧。所以列表在擴容的時候，會將數組申請的長一些，可以在添加元素的時候不用每次都申請新的數組。

這便是列表的底層結構示意圖，我們看到底層數組的長度爲 5，說明此時列表的容量爲 5，但是裏面只有 3 個 PyObject * 指針，說明列表的 ob_size 是 3，或者說列表裏面此時有 3 個元素。

如果這個時候往列表中 append 一個元素，那麼會將這個新元素設置在數組索引爲 ob_size 的位置、或者說索引爲 3 的位置。一旦設置完，ob_size 會自動加 1，因爲 ob_size 要和列表的長度保持一致。

如果此時再往列表中 append 一個元素的話，那麼還是將新元素設置在索引爲 ob_size 的位置，此時也就是索引爲 4 的位置。然後 ob_size 加 1，變成 5。

列表的容量是 5，但此時長度也達到了 5，這說明當下一次 append 的時候，已經沒有辦法再容納新的元素了。因爲此時列表的長度、或者說元素個數已經達到了容量。當然最直觀的還是這裏的底層數組，很明顯全都佔滿了。那這個時候如果想再接收新元素的話，要怎麼辦呢？顯然只能擴容了。

原來的容量是 5，長度也是 5，當再來一個新元素的時候由於沒有位置了，所以要擴容。但是擴容的時候肯定會將容量申請的大一些、即底層數組申請的長一些。

而申請的新的底層數組長度是 9，那麼說明列表的容量就變成了 9。然後將原來數組中的 **PyObject * **按照順序依次拷貝到新的數組裏面，並讓 ob_item 指向新的數組。然後將新元素設置在新數組中索引爲 ob_size 的位置、即索引爲 5 的位置，再將 ob_size 加 1（此時 ob_size 變成了 6）。

以上便是列表底層在擴容的時候所經歷的過程。

並且通過以上幾張圖，我們可以得知列表在 append 之後地址是不變的。因爲如果長度沒有達到容量，那麼 append 其實就是往底層數組中設置了一個新元素；如果達到容量了，那麼會擴容，但擴容只是申請一個新的指針數組，然後讓 ob_item 重新指向罷了。

所以底層的指針數組會變，但 PyListObject 結構體實例本身是沒有變化的。因此列表執行 append, extend, pop, insert 的時候，因爲是本地操作，所以它的地址是不會變化的。

下面我們再來看看列表所佔的內存大小是怎麼算的：

• PyObject_VAR_HEAD：24 字節；

• ob_item：8 字節；

• allocated：8 字節；

所以總共 40 字節，但是不要忘記，在計算列表大小的時候，ob_item 指向的指針數組也要算在內。所以：列表的大小 = 40 + 8 * 指針數組長度 (或者說列表容量)。注意是指針數組長度、或者說列表容量，可不是列表長度，因爲數組一旦申請了，不管你用沒用，大小就擺在那裏了。就好比你租了間房子，就算不住，房租該交還是得交。

# 顯然一個空數組佔40個字節
print([].__sizeof__())  # 40

# 40 + 3 * 8 = 64
print([1, 2, "x" * 1000].__sizeof__())  # 64
#雖然裏面有一個長度爲1000的字符串
#但我們說列表存放的都是指針，所以大小都是8字節

#注意: 我們通過lst = [1, 2, 3]這種方式創建列表的話
#不管內部元素有多少個, 其ob_size和allocated都是一樣的
#只有當列表在添加元素的時候，發現容量不夠了纔會擴容
lst = list(range(10))
# 40 + 10 * 8 = 120
print(lst.__sizeof__())  # 120
# 這個時候append一個元素
lst.append(123)
print(lst.__sizeof__())  # 184
#我們發現大小達到了184, (184 - 40) // 8 = 18
#說明擴容之後申請的數組的長度爲18

所以列表的大小我們就知道是怎麼來的了，以及爲什麼列表在通過索引定位元素的時候，時間複雜度是 O(1)。因爲列表存儲的都是對象的指針，不管對象有多大，其指針大小是固定的，都是 8 字節。通過索引可以瞬間計算出偏移量，從而找到對應元素的指針，而操作指針會自動操作指針所指向的內存。

print([1, 2, 3].__sizeof__())  # 64
print([[1, 2, 3]].__sizeof__())  # 48

相信上面這個結果，你肯定能分析出原因。因爲第一個列表中有 3 個指針，所以大小是 40 + 24 = 64；而第二個列表中有一個指針，所以是 40 + 8 = 48。用一張圖來展示一下 [1, 2, 3] 和 [[1, 2, 3]] 的底層結構，看看它們之間的區別：

到此相信你已經徹底掌握列表的結構了，下面我們來分析一下列表相關操作的時間複雜度。

添加元素

假設有如下這樣一個列表：

我們來看一下它在添加元素的時候，是怎麼表現的。

首先添加元素有很多種方式，其中 append 方法用於向尾部追加一個元素，看一下它的底層實現。

static PyObject *
list_append(PyListObject *self, PyObject *object)
{  
    //顯然調用的app1是核心, 它裏面實現了添加元素的邏輯
    //Py_RETURN_NONE是一個宏，表示返回Python中的None
    //因爲list.append返回的就是None
    if (app1(self, object) == 0)
        Py_RETURN_NONE;
    return NULL;
}

static int
app1(PyListObject *self, PyObject *v)
{  
    //參數self是列表，v是要添加的元素
    //獲取列表的長度
    Py_ssize_t n = PyList_GET_SIZE(self);
    //......
    //因爲v作爲了列表的一個元素，所以其指向的對象的引用計數要加1
    Py_INCREF(v);
    //設置元素，原來的列表長度爲n，最大索引是n - 1
    //那麼追加的話就等於將元素設置在索引爲n的地方
    PyList_SET_ITEM(self, n, v);
    return 0;
}

以上就是 append 的邏輯，所謂插入、追加本質上都是先計算出索引，然後再通過索引設置元素。

如果上面的列表 append 一個 6，就會變成如下：

還是很好理解的。

添加元素除了 append，還可以使用 insert，和只能在尾部追加的 append 不同，該方法可以在任意位置插入。

static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{  
    /*
    參數self：列表
    參數where：索引
    參數v：插入的值
    */
    
    //i是循環變量，n則是當前列表的元素個數
    Py_ssize_t i, n = Py_SIZE(self);
    //指向指針數組的二級指針
    PyObject **items;
    //......
    //確定插入位置
    if (where < 0) {
        //如果where小於0，則加上 n
        //比如有6個元素，where=-1，那麼會加上6，得到5
        //顯然就是insert在索引爲5的位置上 
        where += n;
        //如果喫撐了，寫個 -100，加上元素的個數還是小於0
        if (where < 0)
            //那麼where = 0，就在開頭插入
            where = 0;
    }
    //如果where > n，那麼就在索引爲n的位置插入，
    //可元素個數爲n，最大索引是n-1啊
    //對，所以此時就相當於append
    if (where > n)
        where = n;
    //走到這，索引就確定完了，然後是設置元素
    //拿到原來的二級指針，指向一個指針數組
    items = self->ob_item;
    //然後從where處開始，把索引爲i的值賦值給索引爲i+1
    //相當於元素後移
    //既然是在where處插入，那麼where之前的就不需要動了
    //所以到where處就停止了
    for (i = n; --i >= where; )
        items[i+1] = items[i];
    //增加v指向的對象的引用計數，因爲要被放到列表裏
    Py_INCREF(v);
    //將索引爲where的值設置成v
    items[where] = v;
    return 0;
}

邏輯不難理解，然後是時間複雜度。

• append：顯然時間複雜度爲 O(1)，只是在指定位置寫入一個元素。但需要注意：如果容量不夠了，那麼會擴容，而擴容是一個 O(n) 操作。因此 append 最壞情況下也是一個 O(n) 操作，只不過擴容不會頻繁發生，所以 append 方法的平均時間複雜度還是 O(1)。

• insert：平均時間複雜度是 O(n)，因爲從插入位置開始的每一個元素，都要向後移動；

• extend：這個我們沒有說，但也能夠猜到，它的時間複雜度和 append 是一樣的；

獲取元素

列表支持基於索引獲取元素，這個就比較簡單了。直接拿到底層的指針數組，然後基於索引獲取即可，所以它是一個時間複雜度爲 O(1) 的操作。

當然除了索引，還可以使用切片，只不過切片在底層仍然使用了索引。

# lst[1: 8: 3] 等價於
start = 1
end = 8
step = 3
while start < end:
    item = lst[start]
    # .....
    start += step

因此一些看似高端的操作，在底層實際上並沒有那麼神祕。

設置元素

我們可以獲取指定索引的元素，當然也可以對其進行設置。

# 獲取元素
item = lst[5]
# 設置元素
lst[5] = item

前面說了，添加元素本質上也是通過設置元素實現的。如果列表最大索引爲 n，那麼 append 就等價於在 n + 1 的地方設置元素；而 insert 則是先將待插入位置後面的元素依次後移，然後再將待插入位置設置成指定的元素，本質上也是在不斷地設置元素。

而設置元素的時間複雜度顯然也是 O(1)，當然對一個已存在的元素進行設置，就等價於修改。

另外在設置元素的時候，除了使用索引，還可以使用切片。而在使用切片的時候非常靈活，我們通過 Python 演示一下。

lst = [1, 2, 3, 4, 5, 6, 7, 8]

#首先通過切片進行設置的話
#右值一定要是一個可迭代對象
lst[0: 3] = [11, 22, 33]
# 會將lst[0]設置爲11、lst[1]設置爲22、lst[2]設置爲33
print(lst)  # [11, 22, 33, 4, 5, 6, 7, 8]

#而且它們的長度可以不相等
#這裏表示將[0: 3]的元素設置爲[1, 2]
#其中lst[0]設置成1, lst[1]設置成2
#問題來了, lst[2]咋辦? 
#由於右值中已經沒有元素與之匹配了, 那麼lst[2]就會被刪掉
lst[0: 3] = [1, 2]
print(lst)  # [1, 2, 4, 5, 6, 7, 8]

#所以如果想刪除[0: 3]的元素，那麼只需要執行lst[0: 3] = []即可
#因爲[]裏面沒有元素能與之匹配，所以lst中[0: 3]的位置由於匹配不到
#那麼相當於執行了刪除操作，當然由於Python的動態特性，
#lst[0: 3] = []、lst[0: 3] = ()、lst[0: 3] = "
#都是可以的
lst[0: 3] = ""
print(lst)  # [5, 6, 7, 8]
#實際上我們del lst[0]的時候，就是執行了lst[0: 1] = []

# 當然如果右值元素多的話也是可以的
lst[0: 1] = [1, 2, 3, 4]
print(lst)  # [1, 2, 3, 4, 6, 7, 8]
#將lst[0]設置爲1很好理解, 但此時左邊已經結束了
#所以剩餘的元素會依次插在後面


#然後重點來了, 如果切片有步長的話, 那麼兩邊一定要匹配
#由於此時lst中有7個元素, lst[:: 2]會得到4個元素
#那麼右邊的可迭代對象的長度也必須是4
lst[:: 2] = ['a', 'b', 'c', 'd']
print(lst)  # ['a', 2, 'b', 4, 'c', 7, 'd']

# 但是，如果長度不一致
try:
    lst[:: 2] = ['a', 'b', 'c']
except Exception as e:
    # 顯然會報錯
    print(e)  
# attempt to assign sequence of size 3 to extended slice of size 4

理解起來應該不難，建議去源碼 listobject.c 中看一下具體實現，而在查看的時候，有以下幾個函數，要牢牢地抓住。

• list_subscript：獲取元素時，會調用此函數；

• list_ass_subscript：設置元素時，會調用此函數；

然後這兩個函數即可以接收索引，也可以接收切片：

• 獲取元素時傳入的是索引，那麼 list_subscript 內部會調用 list_item；傳入的是切片，那麼內部會調用 list_slice。

• 設置元素時傳入的是索引，那麼 list_ass_subscript 內部會調用 list_ass_item；傳入的是切片，那麼會調用 list_ass_slice。並且 list_ass_slice 雖然是設置元素，但刪除元素也是調用的它，比如通過 lst[n:n+1]=[] 便可刪除索引爲 n 的元素。事實上 remove、pop 方法都只是計算出待刪除元素的索引，真正的刪除操作還是通過 list_ass_slice 來執行的。

• 另外當傳入切片時，只有步長爲 1，纔會調用 list_slice 和 list_ass_slice；如果步長不爲 1，那麼就採用循環的方式逐個遍歷。

以上就是 Python 在設置元素時的具體實現，雖然是設置元素，但添加和刪除用的也是它。

刪除元素

刪除元素可以使用 pop，默認從尾部彈出元素，當然我們也可以指定索引，彈出指定的元素。

而我們說了 pop 和 del 在刪除元素的時候，會調用 list_ass_slice。

lst = [1, 2, 3, 4, 5]

# 修改元素，在底層相當於修改指針數組中索引爲 4 的元素
lst[4] = 55
print(lst)
"""
[1, 2, 3, 4, 55]
"""

# 添加元素，本質上是將元素設置在索引爲 5 的位置
# 但我們不能執行 lst[5] = 6，因爲索引越界了
# 需要調用 append，由解釋器幫我們設置
lst.append(6)
print(lst)
"""
[1, 2, 3, 4, 55, 6]
"""

# 刪除索引爲 3 的元素
# 可以執行 del lst[3] 或者 lst.pop(3)
# 但它們底層都等價於如下
lst[3: 4] = []
print(lst)
"""
[1, 2, 3, 55, 6]
"""

Python 解釋器是用 C 實現的，而 C 是一門很單純的語言，所以列表的一些花裏胡哨的功能迴歸到 C，就是一些對 C 數組的簡單操作罷了。

列表的擴容

前面說過，當添加元素時，可能會發生容量不夠的情況，因此列表在執行 append 和 insert 方法的時候，都會先檢測列表已存儲的元素個數是否已達到當前容量。一旦達到，那麼要先進行擴容。

而在 list_resize 裏面，它的擴容機制是這樣的。

我們來驗證一下：

lst = [0] * 1000
# 長度和容量一致
print(len(lst))
print((lst.__sizeof__() - 40) // 8)
"""
1000
1000
"""
# 再必須提一下
# 擴容是當解釋器在添加元素時，發現容量不夠的時候纔會擴容
# 而使用 lst = [...] 這種方式創建的列表
# 其大小和容量是相等的

# 但此時添加一個元素的話, 那麼ob_size會變成1001，大於容量1000
# 所以此時列表就要擴容了, 執行 list_resize
# (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
# 顯然 newsize 就是 1001
print(
    1001 + (1001 >> 3) + (3 if 1001 < 9 else 6)
)  # 1132

# append一個元素，列表擴容
lst.append(123)
print((lst.__sizeof__() - 40) // 8)  # 1132

結果是一樣的，因爲底層就是這麼實現的，所以結果必須一樣。只不過我們通過這種測試的方式證明了這一點，也加深了對列表的認識。

介紹完擴容，再來介紹縮容，因爲列表元素個數要是遠小於容量的話，也要進行縮容，否則就會出現內存浪費。那什麼時候縮容呢？答案是當列表的元素個數小於容量的一半時就會縮容。

舉個生活中的例子，假設你租了 10 間屋子用於辦公，顯然你要付 10 間屋子的房租，不管你有沒有用，一旦租了肯定是要付錢的。同理底層數組也是一樣，只要你申請了，不管有沒有存儲元素，內存已經佔用了。

但有一天你用不到 10 間屋子了，假設要用 8 間或者 9 間，那麼會讓剩餘的屋子閒下來。但由於退租比較麻煩，並且只閒下來一兩間屋子，所以乾脆就不退了，還是會付 10 間屋子的錢，這樣沒準哪天又要用的時候就不用重新租了。

對於列表也是如此，在刪除元素（相當於屋子不用了）的時候，如果發現長度還沒有低於容量的一半，那麼也不會縮容。但反之就要縮容了，比如屋子閒了 8 間，也就是隻需要兩間屋子就足夠了，那麼此時肯定要退租了，閒了 8 間，可能會退掉 6 間。

lst = [0] * 1000
print(len(lst))
print((lst.__sizeof__() - 40) // 8)
"""
1000
1000
"""

# 刪除500個元素, 此時長度或者說ob_size就爲500
lst[500:] = []
# 但是ob_size還是達到了容量的一半, 所以不會縮容
print(len(lst))
print((lst.__sizeof__() - 40) // 8)
"""
500
1000
"""

# 如果再刪除一個元素的話, 那麼就要進行縮容了
# 因爲 ob_size 變成了 499, 小於 1000 // 2
# 縮容之後容量怎麼算呢? 還是之前那個公式
print(499 + (499 >> 3) + (3 if 499 < 9 else 6))
"""
567
"""

# 測試一下, 刪除一個元素
# 看看會不會按照我們期待的規則進行縮容
lst.pop()
print(len(lst))
print((lst.__sizeof__() - 40) // 8)
"""
499
567
"""

一切都和我們想的是一樣的，因爲源碼中就是這麼寫的。

最後在源碼中還有一個 if 判斷，就是當列表長度爲 0 的時候，那麼縮容之後的容量也會是 0。

lst = [0] * 1000

lst[:] = []
print(
    len(lst), (lst.__sizeof__() - 40) // 8
)  # 0 0

# 如果按照之前的容量變化公式的話, 會發現結果應該是3
# 但是結果是0, 就是因爲多了if判斷
# 如果newsize是0, 就把容量也設置爲0
print(0 + (0 >> 3) + (3 if 0 < 9 else 6))  # 3

爲什麼要這麼做呢？因爲 Python 認爲，列表長度爲 0 的話，說明你不想用這個列表了，所以多餘的 3 個也沒有必要申請了。還以租房爲例，如果你一間屋子都不用了，說明你可能不用這裏的屋子辦公了，因此直接全部退掉。

小結

以上就是列表的底層實現以及相關操作，這裏再來總結一下。

1）列表在基於索引獲取和設置元素時，時間複雜度是 O(1)，這個效率是極高的，比字典還要快一點。因爲字典在基於 key 操作 value 的時候，也是先對 key 進行哈希，然後映射出一個索引，再基於索引查找。所以哈希表本質上也是一個數組。

我們看到在查找元素時，列表比字典還要快那麼一點點。因爲這兩者在 C 的層面都是基於數組實現的，只不過列表是直接基於索引獲取，而字典則需要多一步對 key 進行映射的過程。當然這兩者的效率都是極高的，複雜度都是 O(1)。

2）列表可以調用 append 追加元素，它的時間複雜度也是 O(1)，只是偶爾會伴隨着擴容。append 的效率也是極高的，比字典寫入元素的效率還要快一點點。

列表寫入 100 萬個元素需要 8.01ms，而字典寫入 100 萬個鍵值對需要 9.97ms。當然兩者單次寫入沒有太大區別，畢竟複雜度都是 O(1)。但列表添加元素使用的要不是 append，而是 insert，那速度就會變慢，因爲它的時間複雜度是 O(n)。

3）因此，如果是基於索引操作的話，那麼列表是沒有任何問題的，但問題在於索引只是一個單純的數字罷了。我們上面舉的例子中，列表的索引和對應元素是相等的，但在工作中我們並不知道某個元素位於列表中的哪個位置，這個時候就只能靠遍歷的方式了。

import time
import numpy as np

def test(count: int, value: int):
    """
    :param count: 循環次數
    :param value: 查詢的元素
    :return:
    """
    # 包含一千個隨機數的列表
    lst = list(np.random.randint(0, 2 ** 30, size=1000))
    # 基於列表構建一個字典
    d = dict.fromkeys(lst)

    # 查詢元素value是否在列表中, 循環count次, 並統計時間
    t1 = time.perf_counter()
    for _ in range(count):
        value in lst
    t2 = time.perf_counter()
    print("列表查詢耗時:", round(t2 - t1, 2))

    # 查詢元素value是否在字典中, 循環count次, 並統計時間
    t1 = time.perf_counter()
    for _ in range(count):
        value in d
    t2 = time.perf_counter()
    print("字典查詢耗時:", round(t2 - t1, 2))


# 分別查詢一千次、一萬次、十萬次、二十萬次
test(10 ** 3, 22333)
"""
列表查詢耗時: 0.13
字典查詢耗時: 0.0
"""
test(10 ** 4, 22333)
"""
列表查詢耗時: 1.22
字典查詢耗時: 0.0
"""
test(10 ** 5, 22333)
"""
列表查詢耗時: 12.68
字典查詢耗時: 0.01
"""
test(10 ** 5 * 2, 22333)
"""
列表查詢耗時: 25.72
字典查詢耗時: 0.01
"""

字典的查詢速度非常快，從測試中我們看到，隨着循環次數越來越多，列表所花費的總時間越來越長。但是字典由於查詢所花費的時間極少，查詢速度非常快，所以即便循環 20 萬次，花費的總時間也不過才 0.01 秒左右。

此外字典還有一個特點，就是它的快不會受到數據量的影響，從含有一萬個鍵值對的字典中查找，和從含有一千萬個鍵值對的字典中查找，兩者花費的時間幾乎是沒有區別的。

原因就是字典在查找元素的時候也是使用了數組的索引，而對於數組來說，基於索引查詢第 0 個元素和第 100w 個元素也是沒有區別的，都是 O(1)。所以字典纔會這麼快，並且不受數據量的影響。

但對於當前來說，列表它不是通過索引來判斷元素是否存在的，而是遍歷每一個元素，然後和指定的元素進行比較。此時它的複雜度就是 O(n)，因此遍歷次數越多，耗時越長。

4）最後是刪除元素，無論是基於索引刪除，還是通過 remove 刪除，時間複雜度都是 O(n)，因爲涉及數據的移動或者比較。而字典仍是 O(1)，字典在刪除元素的時候實際上是僞刪除，只需要將對應的鍵值對標記爲 DUMMY 即可。

以上就是列表和字典的區別，我們下一篇文章再介紹字典是怎麼實現的，加深一遍印象。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/oL32iJGdT4mLhU4vAuwKjA