問題：

“深入認(rèn)識Python內(nèi)建類型”這部分的內(nèi)容會從源碼角度為大家介紹Python中各種常用的內(nèi)建類型。

list是日常開發(fā)中最常用的內(nèi)建類型之一，掌握好它的底層知識，無論是對數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識的理解，還是對開發(fā)效率的提升，應(yīng)該都是有一定幫助的

• list對象支持哪些操作？時(shí)間復(fù)雜度、空間復(fù)雜度分別是多少？
• 試分析append和insert這兩個(gè)典型方法的時(shí)間復(fù)雜度。
• 頭部添加元素時(shí)性能較差，如何解決？

1 常用方法

大家對于list應(yīng)該是比較熟悉的，我們先列舉一些常用的方法：

append：向尾部追加元素

>>> l = [1, 2, 3]
>>> l.append(4)
>>> l
[1, 2, 3, 4]

pop：彈出元素（默認(rèn)從尾部彈出元素，也可以通過index參數(shù)從指定位置彈出）

>>> l = [1, 2, 3, 4]
>>> l.pop()
4
>>> l
[1, 2, 3]

>>> l = [1, 2, 3, 4]
>>> l.pop(0)  # 指定index
1
>>> l
[2, 3, 4]

insert：在指定位置插入元素

>>> l = [1, 2, 3]
>>> l.insert(0, 4)
>>> l
[4, 1, 2, 3]

index：查找指定元素第一次出現(xiàn)位置的下標(biāo)

>>> l = [1, 2, 3, 4]
>>> l.index(1)
0

extend：用一個(gè)可迭代對象擴(kuò)展列表——元素逐一追加到尾部

>>> l = [1, 2, 3]
>>> l.extend({1: 2, 3: 4})
>>> l
[1, 2, 3, 1, 3]

count：計(jì)算元素出現(xiàn)的次數(shù)

>>> l = [1, 2, 3, 1]
>>> l.count(1)
2
>>> l.count(2)
1

reverse：將列表反轉(zhuǎn)（注意這里是直接在原列表上進(jìn)行操作，可以和切片區(qū)分下）

>>> l = [1, 2, 3]
>>> l.reverse()
>>> l
[3, 2, 1]

clear：將列表清空

>>> l = [1, 2, 3]
>>> l.clear()
>>> l
[]

小結(jié)：

list的操作總體比較簡單，但是要注意的是：由于list底層是由數(shù)組實(shí)現(xiàn)的，對應(yīng)的各類插入和刪除操作就會由于數(shù)組的特型而在復(fù)雜度上有所差別，例如：通過insert()在頭部插入元素時(shí)，需要挪動(dòng)整個(gè)列表，此時(shí)時(shí)間復(fù)雜度為O(n)，而append()直接在尾部插入元素時(shí)，時(shí)間復(fù)雜度為O(1)。在使用時(shí)要注意時(shí)空復(fù)雜度問題（后續(xù)我會結(jié)合源碼詳細(xì)介紹）。

題外話：

list的操作有很多，后續(xù)我會對典型操作進(jìn)行源碼分析，還有很多操作可能就需要大家自行去學(xué)習(xí)了解了，但是本質(zhì)上都是大同小異的，掌握好數(shù)組以及Python對此在源碼處理上的一些技巧就能熟練掌握了。這里我結(jié)合自己的學(xué)習(xí)、工作、面試經(jīng)歷，總結(jié)了一點(diǎn)問題和心得：

• list為什么可以使用負(fù)數(shù)索引——從源碼角度看是因?yàn)榕袛嗔怂饕斎霝樨?fù)數(shù)的情況，會做一個(gè)相應(yīng)的處理：索引值+列表長度。例如：索引為-1，列表長度為3，最終的索引就是2，也就是最后一個(gè)元素的索引。對比一下Java中的數(shù)組，如果使用負(fù)數(shù)索引，會報(bào)錯(cuò)索引越界，在網(wǎng)上查能否有相關(guān)方法實(shí)現(xiàn)負(fù)數(shù)索引：有人說用一個(gè)類來包裝，也有的說用一個(gè)字典去映射負(fù)數(shù)和正確的索引，也有的直接給出了無法做到的答案。相關(guān)的做法應(yīng)該是有很多的，但同時(shí)也不要忽視了安全性等相關(guān)問題。這里提出這個(gè)點(diǎn)也是我自己覺得比較有趣的一個(gè)地方吧，“索引值+列表長度”其實(shí)是一個(gè)很簡單的做法，但總感覺又有那么一點(diǎn)一般人想不出來的巧妙，hh
• 以pop()和insert()為例，這兩個(gè)方法有一個(gè)共同的參數(shù)：索引。對于pop()，如果索引值大于等于列表長度，則會報(bào)錯(cuò)；而對于insert()，如果索引值大于等于列表長度則統(tǒng)一將元素插入到列表最后。從源碼角度看其實(shí)就是insert()對于索引參數(shù)做了一個(gè)判斷處理，當(dāng)它大于列表長度時(shí)，會將索引值更改為列表長度，例如：index = 5，而list = [1, 2, 3]，源碼處理時(shí)，會將index置為3。所以如果開發(fā)者樂意的話，應(yīng)該可以對pop()也采用相同的操作，我個(gè)人認(rèn)為這里應(yīng)該是有其他的考慮的，例如安全性等問題，當(dāng)然也有可能只是寫成了這樣而已，hh
• reverse()，reversed()，切片的區(qū)別。個(gè)人認(rèn)為本質(zhì)上這三者其實(shí)沒啥關(guān)系，大家如果容易弄混可能還是因?yàn)椴粔蚴炀?。重點(diǎn)問題可能在切片以及深拷貝、淺拷貝的問題上，后續(xù)我會詳細(xì)介紹相關(guān)內(nèi)容。
• append()和extend()的區(qū)別。面試題好像會問這個(gè)，也是很基礎(chǔ)的知識了。如果換個(gè)角度問可能會更有趣些：l.append(3)和l.extend(3)的效果是不是一樣的？答：不一樣，后者會直接報(bào)錯(cuò)，hh

不知不覺就寫了這么多，相比上次寫str相關(guān)的內(nèi)容還是要順暢多了（捂臉）。相關(guān)的小知識應(yīng)該是還有很多的，大家可以在學(xué)習(xí)的過程中多找一些問題和資料來融會貫通，當(dāng)然我個(gè)人認(rèn)為如果能把底層的邏輯搞清楚，其他的應(yīng)該都不成問題~

2 list的內(nèi)部結(jié)構(gòu)：PyListObject

源碼如下：

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;

源碼分析：

• ob_item：二維指針，指向動(dòng)態(tài)數(shù)組的指針，數(shù)組保存元素對象指針
• allocated：動(dòng)態(tài)數(shù)組總長度，即列表當(dāng)前的容量
• ob_size：當(dāng)前元素個(gè)數(shù)，即列表當(dāng)前的長度

這里出現(xiàn)了一些新的概念：動(dòng)態(tài)數(shù)組，容量。后續(xù)我會對此進(jìn)行介紹，這里大家對照示意圖應(yīng)該就能有比較初步的認(rèn)識了：

3 尾部操作和頭部操作

認(rèn)識了list的底層結(jié)構(gòu)之后，這里在強(qiáng)調(diào)一下尾部操作和頭部操作的一些問題，鞏固一下數(shù)組相關(guān)的數(shù)據(jù)結(jié)構(gòu)知識，也順便引出一些動(dòng)態(tài)數(shù)組的相關(guān)內(nèi)容。

3.1 尾部操作

假設(shè)列表對象 l 內(nèi)部數(shù)組長度為5，當(dāng)前保存了2個(gè)元素，分別是1，2。當(dāng)我們調(diào)用append()方法向尾部追加元素時(shí)，由于內(nèi)部數(shù)組還未用滿，只需將新元素保存于下一個(gè)可用位置，并更新ob_size字段。因此，絕大多數(shù)情況下，append()方法的性能都足夠好，時(shí)間復(fù)雜度為O(1)。

若list對象內(nèi)部數(shù)組已滿，則再添加元素時(shí)就需要進(jìn)行擴(kuò)容。append()等方法在操作時(shí)都會對內(nèi)部數(shù)組進(jìn)行檢查，如需擴(kuò)容，則會重新分配一個(gè)長度更大的數(shù)組并替換舊數(shù)組。因此，當(dāng)使用append()方法遇到擴(kuò)容時(shí)，會將列表元素從舊數(shù)組拷貝到新數(shù)組，此時(shí)時(shí)間復(fù)雜度為O(n)。

個(gè)人想法：這里引出這個(gè)問題是因?yàn)槲覀€(gè)人當(dāng)時(shí)在學(xué)習(xí)到這個(gè)知識點(diǎn)時(shí)，意識到了一個(gè)問題：怎么擴(kuò)容。如果沒記錯(cuò)的話Java面試題中也會經(jīng)常聞到動(dòng)態(tài)擴(kuò)容。這里拋開面試不談，我的想法主要是在怎么去避免頻繁擴(kuò)容，畢竟擴(kuò)容一次就需要拷貝所有的元素。這在日常開發(fā)中應(yīng)該也是一個(gè)需要大家關(guān)注的問題：像這種類似的消耗突增的操作，我們需要去避免，降低它的觸發(fā)頻率，但同時(shí)也不能忽視時(shí)空上的消耗。

3.2 頭部操作

與尾部相比，由于在列表頭部增刪元素需要挪動(dòng)其他元素，性能差別就很大了（數(shù)組的基礎(chǔ)知識）

這里既然提到了頭部操作，我們來看一下Python中的隊(duì)列：

通過list實(shí)現(xiàn)棧是很好的，但是用來實(shí)現(xiàn)隊(duì)列是很不合理的：（LeetCode上的用棧實(shí)現(xiàn)隊(duì)列除外，hh）

q = []
q.append(1)
q.append(2)
q.append(3)
# deque
q.pop(0)

這樣的隊(duì)列實(shí)現(xiàn)，在出隊(duì)操作時(shí)會移動(dòng)所有隊(duì)列元素（除pop掉的元素以外），性能很差

如果需要頻繁進(jìn)行頭部操作，可以使用標(biāo)準(zhǔn)庫中的deque，這是一種雙端隊(duì)列結(jié)構(gòu)：

from collections import deque
q = deque()
# enqueue
q.append(job)
# deque
q.popleft()

4 淺拷貝和深拷貝

淺拷貝和深拷貝應(yīng)該是容器相關(guān)的一個(gè)比較重要的知識點(diǎn)了，無論是Python還是Java中都會涉及，面試中應(yīng)該也比較常見。（其實(shí)可以單獨(dú)寫一篇博客來介紹這部分內(nèi)容，這里就先放在了list中來介紹，后續(xù)會考慮重新總結(jié)歸納出一篇博客）

4.1 淺拷貝

調(diào)用list對象的copy方法，可以將列表拷貝一份，生成一個(gè)新的列表，但是不會拷貝列表中的元素。結(jié)合源碼來說就是：會拷貝一下底層數(shù)組中指向具體元素對象的指針，但是元素對象不會被拷貝。

下面通過對淺拷貝后的列表進(jìn)行修改來實(shí)際體會一下：

示例1：

>>> l1 = [1, [1, 2, 3]]
>>> l1
[1, [1, 2, 3]]
# 淺拷貝
>>> l2 = l1.copy()
>>> l2
[1, [1, 2, 3]]
# 修改新列表中的可變元素
>>> l2[1][0] = 6
>>> l2
[1, [6, 2, 3]]
>>> l1
[1, [6, 2, 3]]

示例2：

>>> l1 = [1, [1, 2, 3]]
>>> l1
[1, [1, 2, 3]]
# 淺拷貝
>>> l2 = l1.copy()
>>> l2
[1, [1, 2, 3]]
# 修改新列表中的不可變元素
>>> l2[0] = 2
>>> l2
[2, [1, 2, 3]]
>>> l1
[1, [1, 2, 3]]

示例3：

>>> l1 = [1, [1, 2, 3]]
>>> l1
[1, [1, 2, 3]]
# 淺拷貝
>>> l2 = l1.copy()
>>> l2
[1, [1, 2, 3]]
# 這里要注意并沒有修改可變元素[1, 2, 3]，而是將l2[1]處的指針修改了，指向了一個(gè)新對象[3, 4]
>>> l2[1] = [3, 4]
>>> l2
[2, [3, 4]]
>>> l1
[1, [1, 2, 3]]

list對象的底層數(shù)組保存的是元素對象的指針，copy()方法復(fù)制底層數(shù)組時(shí)，拷貝的也是元素對象的指針，而不會拷貝具體的元素對象。因此，新舊列表對象的數(shù)組中的指針指向的還是相同的對象。圖示如下：

4.2 深拷貝

通過copy模塊中的deepcopy()函數(shù)可以進(jìn)行深拷貝，deepcopy()函數(shù)會遞歸復(fù)制所有容器對象，確保新舊列表不會包含同一個(gè)容器對象（這里要注意元組是比較特殊的，稍微會說明）

下面通過對深拷貝后的列表進(jìn)行修改來實(shí)際體會一下：

>>> from copy import deepcopy
>>> l1 = [1, [1, 2, 3]]
>>> l1
[1, [1, 2, 3]]
# 深拷貝
>>> l2 = deepcopy(l1)
>>> l2
[1, [1, 2, 3]]
>>> l2[1][0] = 5
>>> l2
[1, [5, 2, 3]]
>>> l1
[1, [1, 2, 3]]
>>> l2[0] = 2
>>> l2
[2, [5, 2, 3]]
>>> l1
[1, [1, 2, 3]]

圖示如下：

4.3 直接賦值

除了深拷貝、淺拷貝外，最常見的操作就是直接賦值，即對象的引用（別名），這里就不涉及到復(fù)制操作了。

4.4 小結(jié)

直接賦值：b = a

淺拷貝：b = a.copy()

深拷貝：b = copy.deepcopy(a)

個(gè)人總結(jié)：

弄清楚list底層數(shù)組中存儲的是指向?qū)?yīng)元素的指針，以及深拷貝時(shí)的遞歸，我覺得就能對相關(guān)的知識點(diǎn)有一個(gè)比較清晰的認(rèn)識了。但是對于Python中的元組需要特殊考慮，它是一個(gè)不可變的容器，當(dāng)元組中含有可變數(shù)據(jù)類型的容器和不含時(shí)，深拷貝的情況是有區(qū)別的。

本質(zhì)上元組是不會去創(chuàng)建新對象的，因?yàn)樗豢勺儯ㄟ@里我沒有找到百分百的證據(jù)，主要是根據(jù)經(jīng)驗(yàn)和查到的資料，大家可以去看一下源碼），但是當(dāng)元組中還有可變數(shù)據(jù)類型的容器，就又會由于深拷貝遞歸去拷貝相應(yīng)的對象而導(dǎo)致重新創(chuàng)建一個(gè)新的元組對象。

這里可能比較繞，大家可以自行去打印看一下結(jié)果。但是我個(gè)人覺得核心就是“弄清楚list底層數(shù)組中存儲的是指向?qū)?yīng)元素的指針，以及深拷貝時(shí)的遞歸”。

TODO：

后續(xù)我會重新寫一篇博客來專門將深淺拷貝的源碼列出來，來看看為什么對于元組就會特殊處理。

要是我們的列表元素是自定義的數(shù)據(jù)類型又是如何處理的。深拷貝遞歸復(fù)制時(shí)判斷的條件到底是如何寫的。

5 動(dòng)態(tài)數(shù)組

這一部分的內(nèi)容也是這篇博客最主要的重點(diǎn)：分析list底層數(shù)組的特性。前面我們已經(jīng)介紹了list的常用操作、底層結(jié)構(gòu)，以及以list為例簡單介紹了深淺拷貝。這一小節(jié)會結(jié)合源碼詳細(xì)介紹list底層動(dòng)態(tài)數(shù)組的特性，我個(gè)人覺得這一設(shè)計(jì)也傳達(dá)了我們在業(yè)務(wù)開發(fā)上的一個(gè)比較常用和關(guān)鍵的思想。

5.1 容量調(diào)整

前面已經(jīng)提到，當(dāng)我們調(diào)用append()、pop()、insert()等方法時(shí)，列表長度會發(fā)生變化。當(dāng)列表長度超過底層數(shù)組容量時(shí)，便需要對底層數(shù)組進(jìn)行擴(kuò)容；當(dāng)列表長度低于底層數(shù)組容量并且達(dá)到某個(gè)值時(shí)，便需要對底層數(shù)組進(jìn)行縮容。

append()等方法是依賴list_resize()函數(shù)來調(diào)整列表長度的。源碼如下：

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    PyObject **items;
    size_t new_allocated, num_allocated_bytes;
    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.
    */
    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, ...
     * Note: new_allocated won't overflow because the largest possible value
     *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
     */
    new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
    if (new_allocated > (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {
        PyErr_NoMemory();
        return -1;
    }

    if (newsize == 0)
        new_allocated = 0;
    num_allocated_bytes = new_allocated * sizeof(PyObject *);
    items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
}

源碼分析：

重要參數(shù)：

• items指針：用于保存新數(shù)組
• new_allocated：用于保存新數(shù)組容量
• num_allocated_bytes：用于保存新數(shù)組內(nèi)存大小，單位為字節(jié)
• allocated：用于保存舊數(shù)組容量

重要步驟：

第12行：檢查新長度與底層數(shù)組容量的大小關(guān)系。如果新長度不超過現(xiàn)有數(shù)組容量，并且大于等于現(xiàn)有容量的一半，則不會更新數(shù)組容量，只修改ob_size即可。從這里我們可以得知list對象的擴(kuò)縮容條件：

• 擴(kuò)容條件：新長度大于底層數(shù)組容量
• 縮容條件：新長度小于底層數(shù)組容量的一半

第27行：新容量=新長度+1/8*新長度+3或6（取決于新長度是否小于9）

第28~31行：如果新容量超過了允許的最大值，則返回錯(cuò)誤

第33~34行：如果新長度為0，則新容量也為0，此時(shí)底層數(shù)組為空

第36~40行：調(diào)用PyMem_Realloc()函數(shù)重新分配底層數(shù)組

第41~44行：依次設(shè)置新底層數(shù)組、新長度、新容量

注：

在擴(kuò)容時(shí)先增加1/8，再增加3或6，是為了有效限制擴(kuò)容頻率，避免list對象長度較小時(shí)會頻繁擴(kuò)容（我個(gè)人在工作中沒有遇到需要考慮類似問題的需求，都是在寫業(yè)務(wù)代碼（捂臉），但是我認(rèn)為這種思想還是值得學(xué)習(xí)的）

PyMem_Realloc()函數(shù)是Python內(nèi)部實(shí)現(xiàn)的內(nèi)存管理函數(shù)之一，功能和C的庫函數(shù)realloc()類似。主要步驟如下：

PyAPI_FUNC(void *) PyMem_Realloc(void *ptr, size_t new_size);

新申請一塊大小為new_size的內(nèi)存區(qū)域?qū)?shù)據(jù)從舊內(nèi)存區(qū)域ptr拷貝到新內(nèi)存區(qū)域釋放舊內(nèi)存區(qū)域ptr返回新內(nèi)存區(qū)域

圖示如下：

5.2 append()

append()方法在Python內(nèi)部由C函數(shù)list_append()實(shí)現(xiàn)，而list_append()進(jìn)一步調(diào)用app1()函數(shù)完成元素追加

app1()函數(shù)源碼如下：

static int
app1(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) < 0)
        return -1;

    Py_INCREF(v);
    PyList_SET_ITEM(self, n, v);
    return 0;
}

源碼分析：

第4行：調(diào)用PyList_GET_SIZE()獲取列表當(dāng)前長度，即ob_size

第7~11行：如果列表當(dāng)前長度達(dá)到了最大值PY_SSIZE_T_MAX，則報(bào)錯(cuò)

第13~14行：調(diào)用list_resize()，必要時(shí)進(jìn)行擴(kuò)容

第16行：增加元素對象引用計(jì)數(shù)（這里是列表引用了該元素對象）

第17行：調(diào)用PyList_SET_ITEM()將元素對象指針保存在列表的最后一個(gè)位置

5.3 insert()

insert()方法在Python內(nèi)部由C函數(shù)list_insert_impl()實(shí)現(xiàn)，而list_insert_impl()進(jìn)一步調(diào)用ins1()函數(shù)完成元素插入

ins1()函數(shù)源碼如下：

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;
    }

    if (list_resize(self, n+1) < 0)
        return -1;

    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];
    Py_INCREF(v);
    items[where] = v;
    return 0;
}

源碼分析：

第19~25行：檢查插入位置下標(biāo)，如果下標(biāo)為負(fù)數(shù)，則加上n將其轉(zhuǎn)化為非負(fù)數(shù)。如果轉(zhuǎn)化后的where值仍然小于0，則代表越界，但是這里會直接將where設(shè)置為0（即插入到列表頭部），而沒有報(bào)錯(cuò)。若下標(biāo)為正數(shù)，也會判斷是否越界，越界時(shí)則插入到列表尾部，同樣不會報(bào)錯(cuò)。

第26~28行：將插入位置以后的元素逐一往后移動(dòng)一個(gè)位置。（這里的for循環(huán)是從后往前迭代的）

5.4 pop()

pop()方法將指定下標(biāo)的元素從列表中彈出，下標(biāo)默認(rèn)為-1，即默認(rèn)彈出最后一個(gè)元素

pop()方法在Python內(nèi)部由list_pop_impl()函數(shù)實(shí)現(xiàn)。源碼如下：

static PyObject *
list_pop_impl(PyListObject *self, Py_ssize_t index)
/*[clinic end generated code: output=6bd69dcb3f17eca8 input=b83675976f329e6f]*/
{
    PyObject *v;
    int status;

    if (Py_SIZE(self) == 0) {
        /* Special-case most common failure cause */
        PyErr_SetString(PyExc_IndexError, "pop from empty list");
        return NULL;
    }
    if (index < 0)
        index += Py_SIZE(self);
    if (index < 0 || index >= Py_SIZE(self)) {
        PyErr_SetString(PyExc_IndexError, "pop index out of range");
        return NULL;
    }
    v = self->ob_item[index];
    if (index == Py_SIZE(self) - 1) {
        status = list_resize(self, Py_SIZE(self) - 1);
        if (status >= 0)
            return v; /* and v now owns the reference the list had */
        else
            return NULL;
    }
    Py_INCREF(v);
    status = list_ass_slice(self, index, index+1, (PyObject *)NULL);
    if (status < 0) {
        Py_DECREF(v);
        return NULL;
    }
    return v;
}

源碼分析：

第12~13行：如果給定下標(biāo)為負(fù)數(shù)，則加上列表長度，轉(zhuǎn)化為普通下標(biāo)

第14~16行：檢查下標(biāo)是否合法，如果越界則報(bào)錯(cuò)

第19~25行：如果待彈出元素為列表的尾部元素，則調(diào)用list_resize()直接處理（比較巧妙，hh）

第26~31行：其他情況下調(diào)用list_ass_slice()刪除元素，調(diào)用前需要通過Py_INCREF增加元素的引用計(jì)數(shù)，因?yàn)樵趌ist_ass_slice()函數(shù)內(nèi)部會釋放被刪除元素

5.5 remove()

remove()方法將給定元素從列表中刪除，與pop()不同，remove()直接刪除給定元素，而不是通過下標(biāo)進(jìn)行索引

remove()方法在Python內(nèi)部由C函數(shù)list_remove()實(shí)現(xiàn)。源碼如下：

static PyObject *
list_remove(PyListObject *self, PyObject *value)
/*[clinic end generated code: output=f087e1951a5e30d1 input=2dc2ba5bb2fb1f82]*/
{
    Py_ssize_t i;

    for (i = 0; i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], value, 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;
    }
    PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
    return NULL;
}

源碼分析：

第7行：通過for循環(huán)查找目標(biāo)元素是否在列表中，若不在則會報(bào)錯(cuò)第

10行：通過list_ass_slice()刪除指定元素

6 一些問題

擴(kuò)容時(shí)參數(shù)選擇的依據(jù)？

答：兼顧內(nèi)存利用率和擴(kuò)容頻率。

淺拷貝：

static PyObject *
list_remove(PyListObject *self, PyObject *value)
/*[clinic end generated code: output=f087e1951a5e30d1 input=2dc2ba5bb2fb1f82]*/
{
    Py_ssize_t i;

    for (i = 0; i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], value, 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;
    }
    PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
    return NULL;
}

聲明一個(gè)空列表l = []，Python是如何為它分配空間的？

答：對于這類問題，有兩種策略：

預(yù)先分配一定大小的動(dòng)態(tài)數(shù)組，對于最開始的增加元素操作不需要立即擴(kuò)容；

開始時(shí)不分配動(dòng)態(tài)數(shù)組，第一次添加元素時(shí)就會擴(kuò)容。Python采用的是策略主要是為了將動(dòng)態(tài)數(shù)組的分配推遲到真正需要的時(shí)刻，提高內(nèi)存的使用效率。程序設(shè)計(jì)中的懶加載，操作系統(tǒng)的fork進(jìn)程后采用的copy on write策略，指導(dǎo)思想都是類似的。（日常開發(fā)中這個(gè)思想應(yīng)該也是有一定用處的）

以上就是Python內(nèi)建類型list源碼學(xué)習(xí)的詳細(xì)內(nèi)容，更多關(guān)于Python內(nèi)建類型list的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論