本文將介紹列表在 CPython中的實(shí)現(xiàn),因?yàn)楫吘?/span>Cpython 又是 Python 最為常用的實(shí)現(xiàn),一起來看看吧,希望對(duì)大家學(xué)習(xí)python有所幫助。
Python 中的列表非常強(qiáng)大,看看它的內(nèi)部實(shí)現(xiàn)機(jī)制是怎么樣的,一定非常有趣。
下面是一段 Python 腳本,在列表中添加幾個(gè)整數(shù),然后打印列表。
>>> l = []
>>> l.append(1)
>>> l.append(2)
>>> l.append(3)
>>> l
[1, 2, 3]
>>> for e in l:
... print e
...
1
2
3
可以發(fā)現(xiàn),列表是一個(gè)迭代器。
列表對(duì)象的 C 語言結(jié)構(gòu)體
Cpython 中的列表實(shí)現(xiàn)類似于下面的 C 結(jié)構(gòu)體。ob_item 是指向列表對(duì)象的指針數(shù)組。allocated 是申請(qǐng)內(nèi)存的槽的個(gè)數(shù)。
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
列表初始化
看看初始化一個(gè)空列表的時(shí)候發(fā)生了什么,例如:l = []。
arguments: size of the list = 0
returns: list object = []
PyListNew:
nbytes = size * size of global Python object = 0
allocate new list object
allocate list of pointers (ob_item) of size nbytes = 0
clear ob_item
set list's allocated var to 0 = 0 slots
return list object
要分清列表大小和分配的槽大小,這很重要。列表的大小和 len(l) 的大小相同。分配槽的大小是指已經(jīng)在內(nèi)存中分配了的槽空間數(shù)。通常分配的槽的大小要大于列表大小,這是為了避免每次列表添加元素的時(shí)候都調(diào)用分配內(nèi)存的函數(shù)。下面會(huì)具體介紹。
Append 操作
向列表添加一個(gè)整數(shù):l.append(1) 時(shí)發(fā)生了什么?調(diào)用了底層的 C 函數(shù) app1()。
arguments: list object, new element
returns: 0 if OK, -1 if not
app1:
n = size of list
call list_resize() to resize the list to size n+1 = 0 + 1 = 1
list[n] = list[0] = new element
return 0
下面是 list_resize() 函數(shù)。它會(huì)多申請(qǐng)一些內(nèi)存,避免頻繁調(diào)用 list_resize() 函數(shù)。列表的增長模式為:0,4,8,16,25,35,46,58,72,88……
arguments: list object, new size
returns: 0 if OK, -1 if not
list_resize:
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) = 3
new_allocated += newsize = 3 + 1 = 4
resize ob_item (list of pointers) to size new_allocated
return 0
現(xiàn)在分配了 4 個(gè)用來裝列表元素的槽空間,并且第一個(gè)空間中為整數(shù) 1。如下圖顯示 l[0] 指向我們新添加的整數(shù)對(duì)象。虛線的方框表示已經(jīng)分配但沒有使用的槽空間。
列表追加元素操作的平均復(fù)雜度為 O(1)。
繼續(xù)添加新的元素:l.append(2)。調(diào)用 list_resize 函數(shù),參數(shù)為 n+1 = 2, 但是因?yàn)橐呀?jīng)申請(qǐng)了 4 個(gè)槽空間,所以不需要再申請(qǐng)內(nèi)存空間。再添加兩個(gè)整數(shù)的情況也是一樣的:l.append(3),l.append(4)。下圖顯示了我們現(xiàn)在的情況。
Insert 操作
在列表偏移量 1 的位置插入新元素,整數(shù) 5:l.insert(1,5),內(nèi)部調(diào)用ins1() 函數(shù)。
arguments: list object, where, new element
returns: 0 if OK, -1 if not
ins1:
resize list to size n+1 = 5 -> 4 more slots will be allocated
starting at the last element up to the offset where, right shift each element
set new element at offset where
return 0
虛線的方框依舊表示已經(jīng)分配但沒有使用的槽空間?,F(xiàn)在分配了 8 個(gè)槽空間,但是列表的大小卻只是 5。
列表插入操作的平均復(fù)雜度為 O(n)。
Pop 操作
取出列表最后一個(gè)元素 即l.pop(),調(diào)用了 listpop() 函數(shù)。在 listpop() 函數(shù)中會(huì)調(diào)用 list_resize 函數(shù),如果取出元素后列表的大小小于分配的槽空間數(shù)的一半,將會(huì)縮減列表的大小。
arguments: list object
returns: element popped
listpop:
if list empty:
return null
resize list with size 5 - 1 = 4. 4 is not less than 8/2 so no shrinkage
set list object size to 4
return last element
列表 pop 操作的平均復(fù)雜度為 O(1)。
可以看到 pop 操作后槽空間 4 依然指向原先的整數(shù)對(duì)象,但是最為關(guān)鍵的是現(xiàn)在列表的大小已經(jīng)變?yōu)?4。
繼續(xù) pop 一個(gè)元素。在 list_resize() 函數(shù)中,size – 1 = 4 – 1 = 3 已經(jīng)小于所分配的槽空間大小的一半,所以縮減分配的槽空間為 6,同時(shí)現(xiàn)在列表的大小為 3。
可以看到槽空間 3 和 4 依然指向原先的整數(shù),但是現(xiàn)在列表的大小已經(jīng)變?yōu)?3。
Remove 操作
Python 的列表對(duì)象有個(gè)方法,刪除指定的元素: l.remove(5)。底層調(diào)用 listremove() 函數(shù)。
arguments: list object, element to remove
returns none if OK, null if not
listremove:
loop through each list element:
if correct element:
slice list between element's slot and element's slot + 1
return none
return null
為了做列表的切片并且刪除元素,調(diào)用了 list_ass_slice() 函數(shù),它的實(shí)現(xiàn)方法比較有趣。我們?cè)趧h除列表位置 1 的元素 5 的時(shí)候,低位的偏移量為 1 同時(shí)高位的偏移量為 2.
arguments: list object, low offset, high offset
returns: 0 if OK
list_ass_slice:
copy integer 5 to recycle list to dereference it
shift elements from slot 2 to slot 1
resize list to 5 slots
return 0
列表 remove 操作的復(fù)雜度為 O(n)。
來源:51CTO