Python內(nèi)建類型list源碼學(xué)習(xí)

第Python內(nèi)建類型list源碼學(xué)習(xí)目錄問題：1常用方法小結(jié)：題外話：2list的內(nèi)部結(jié)構(gòu)：PyListObject3尾部操作和頭部操作3.1尾部操作3.2頭部操作4淺拷貝和深拷貝4.1淺拷貝4.2深拷貝4.3直接賦值4.4小結(jié)個人總結(jié)：TODO：5動態(tài)數(shù)組5.1容量調(diào)整5.2append()5.3insert()5.4pop()5.5remove()6一些問題

問題：

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

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

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

1常用方法

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

append：向尾部追加元素

l=[1,2,3]

l.append(4)

[1,2,3,4]

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

l=[1,2,3,4]

l.pop()

[1,2,3]

l=[1,2,3,4]

l.pop(0)#指定index

[2,3,4]

insert：在指定位置插入元素

l=[1,2,3]

l.insert(0,4)

[4,1,2,3]

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

l=[1,2,3,4]

l.index(1)

extend：用一個可迭代對象擴展列表元素逐一追加到尾部

l=[1,2,3]

l.extend({1:2,3:4})

[1,2,3,1,3]

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

l=[1,2,3,1]

l.count(1)

l.count(2)

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

l=[1,2,3]

l.reverse()

[3,2,1]

clear：將列表清空

l=[1,2,3]

l.clear()

小結(jié)：

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

題外話：

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

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

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

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

源碼如下：

typedefstruct{

PyObject_VAR_HEAD

/*Vectorofpointerstolistelements.list[0]isob_item[0],etc.*/

PyObject**ob_item;

/*ob_itemcontainsspacefor'allocated'elements.Thenumber

*currentlyinuseisob_size.

*Invariants:

*0=ob_size=allocated

*len(list)==ob_size

*ob_item==NULLimpliesob_size==allocated==0

*list.sort()temporarilysetsallocatedto-1todetectmutations.

*ItemsmustnormallynotbeNULL,exceptduringconstructionwhen

*thelistisnotyetvisibleoutsidethefunctionthatbuildsit.

Py_ssize_tallocated;

}PyListObject;

源碼分析：

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

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

3尾部操作和頭部操作

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

3.1尾部操作

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

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

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

3.2頭部操作

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

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

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

q=[]

q.append(1)

q.append(2)

q.append(3)

#deque

q.pop(0)

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

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

fromcollectionsimportdeque

q=deque()

#enqueue

q.append(job)

#deque

q.popleft()

4淺拷貝和深拷貝

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

4.1淺拷貝

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

下面通過對淺拷貝后的列表進行修改來實際體會一下：

示例1：

l1=[1,[1,2,3]]

[1,[1,2,3]]

#淺拷貝

l2=l1.copy()

[1,[1,2,3]]

#修改新列表中的可變元素

l2[1][0]=6

[1,[6,2,3]]

[1,[6,2,3]]

示例2：

l1=[1,[1,2,3]]

[1,[1,2,3]]

#淺拷貝

l2=l1.copy()

[1,[1,2,3]]

#修改新列表中的不可變元素

l2[0]=2

[2,[1,2,3]]

[1,[1,2,3]]

示例3：

l1=[1,[1,2,3]]

[1,[1,2,3]]

#淺拷貝

l2=l1.copy()

[1,[1,2,3]]

#這里要注意并沒有修改可變元素[1,2,3]，而是將l2[1]處的指針修改了，指向了一個新對象[3,4]

l2[1]=[3,4]

[2,[3,4]]

[1,[1,2,3]]

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

4.2深拷貝

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

下面通過對深拷貝后的列表進行修改來實際體會一下：

fromcopyimportdeepcopy

l1=[1,[1,2,3]]

[1,[1,2,3]]

#深拷貝

l2=deepcopy(l1)

[1,[1,2,3]]

l2[1][0]=5

[1,[5,2,3]]

[1,[1,2,3]]

l2[0]=2

[2,[5,2,3]]

[1,[1,2,3]]

圖示如下：

4.3直接賦值

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

4.4小結(jié)

直接賦值：b=a

淺拷貝：b=a.copy()

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

個人總結(jié)：

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

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

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

TODO：

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

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

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

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

5.1容量調(diào)整

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

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

staticint

list_resize(PyListObject*self,Py_ssize_tnewsize)

PyObject**items;

size_tnew_allocated,num_allocated_bytes;

Py_ssize_tallocated=self-allocated;

/*Bypassrealloc()whenapreviousoverallocationislargeenough

toaccommodatethenewsize.Ifthenewsizefallslowerthanhalf

theallocatedsize,thenproceedwiththerealloc()toshrinkthelist.

if(allocated=newsizenewsize=(allocated1)){

assert(self-ob_item!=NULL||newsize==0);

Py_SIZE(self)=newsize;

return0;

/*Thisover-allocatesproportionaltothelistsize,makingroom

*foradditionalgrowth.Theover-allocationismild,butis

*enoughtogivelinear-timeamortizedbehavioroveralong

*sequenceofappends()inthepresenceofapoorly-performing

*systemrealloc().

*Thegrowthpatternis:0,4,8,16,25,35,46,58,72,88,...

*Note:new_allocatedwon'toverflowbecausethelargestpossiblevalue

*isPY_SSIZE_T_MAX*(9/8)+6whichalwaysfitsinasize_t.

new_allocated=(size_t)newsize+(newsize3)+(newsize93: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;

return0;

源碼分析：

重要參數(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對象的擴縮容條件：

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

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

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

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

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

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

注：

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

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

PyAPI_FUNC(void*)PyMem_Realloc(void*ptr,size_tnew_size);

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

圖示如下：

5.2append()

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

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

staticint

app1(PyListObject*self,PyObject*v)

Py_ssize_tn=PyList_GET_SIZE(self);

assert(v!=NULL);

if(n==PY_SSIZE_T_MAX){

PyErr_SetString(PyExc_OverflowError,

"cannotaddmoreobjectstolist");

return-1;

if(list_resize(self,n+1)0)

return-1;

Py_INCREF(v);

PyList_SET_ITEM(self,n,v);

return0;

源碼分析：

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

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

第13~14行：調(diào)用list_resize()，必要時進行擴容

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

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

5.3insert()

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

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

staticint

ins1(PyListObject*self,Py_ssize_twhere,PyObject*v)

Py_ssize_ti,n=Py_SIZE(self);

PyObject**items;

if(v==NULL){

PyErr_BadInternalCall();

return-1;

if(n==PY_SSIZE_T_MAX){

PyErr_SetString(PyExc_OverflowError,

"cannotaddmoreobjectstolist");

return-1;

if(list_resize(self,n+1)0)

return-1;

if(where0){

where+=n;

if(where0)

where=0;

if(wheren)

where=n;

items=self-ob_item;

for(i=n;--i=where;)

items[i+1]=items[i];

Py_INCREF(v);

items[where]=v;

return0;

源碼分析：

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

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

5.4pop()

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

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

staticPyObject*

list_pop_impl(PyListObject*self,Py_ssize_tindex)

/*[clinicendgeneratedcode:output=6bd69dcb3f17eca8input=b83675976f329e6f]*/

PyObject*v;

intstatus;

if(Py_SIZE(self)==0){

/*Special-casemostcommonfailurecause*/

PyErr_SetString(PyExc_IndexError,"popfromemptylist");

returnNULL;

if(index0)

index+=Py_SIZE(self);

if(index0||index=Py_SIZE(self)){

PyErr_SetString(PyExc_IndexError,"popindexoutofrange");

returnNULL;

v=self-ob_item[index];

if(index==Py_SIZE(self)-1){

status=list_resize(self,Py_SIZE(self)-1);

if(status=0)

returnv;/*andvnowownsthereferencethelisthad*/

else

returnNULL;

Py_INCREF(v);

status=list_ass_slice(self,index,index+1,(PyObject*)NULL);

if(status0){

Py_DECREF(v);

returnNULL;

returnv;

源碼分析：

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

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

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

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

5.5remove()

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

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

staticPyObject*

list_remove(PyListObject*self,PyObject*value)

/*[clinicendgeneratedcode:output=f087e1951a5e30d1input=2dc2ba5bb2fb1f82]*/

Py_ssize_ti;

for