Python中list的實現

原文鏈接
這篇文章介紹了Python中list是如何實現的。
在Python中list特別有用。讓我們來看下list的內部是如何實現的。
來看下麵簡單的程式，在list中添加一些整數並將他們列印出來。

>>> L = []
>>> L.append(1)
>>> L.append(2)
>>> L.append(3)
>>> L
[1, 2, 3]
>>> for e in L:
...   print e
... 
1   
2   
3   

正如你所看到的，list是可以迭代的。

List對象的C結構

Python中list是用下邊的C語言的結構來表示的。ob_item是用來保存元素的指針數組，allocated是ob_item預先分配的記憶體總容量

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

List的初始化

讓我們來看下當初始化一個空list的時候發生了什麼 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 

非常重要的是知道list申請記憶體空間的大小（後文用allocated代替）的大小和list實際存儲元素所占空間的大小(ob_size)之間的關係，ob_size的大小和len(L)是一樣的，而allocated的大小是在記憶體中已經申請空間大小。通常你會看到allocated的值要比ob_size的值要大。這是為了避免每次有新元素加入list時都要調用realloc進行記憶體分配。接下來我們會看到更多關於這些的內容。

Append

我們在list中追加一個整數:L.append(1)。發生了什麼？調用了內部的C函數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(),list_resize()會申請多餘的空間以避免調用多次list_resize()函數，list增長的模型是: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

開闢了四個記憶體空間來存放list中的元素，存放的第一個元素是1。你可以從下圖中看到L[0]指向了我們剛剛加進去的元素。虛線的框代表了申請了但是還沒有使用(存儲元素)的記憶體空間

我們繼續加入一個元素：L.append(2)。調用list_resize,同時n+1=2。但是因為allocated（譯者註：已經申請的空間大小）是4。所以沒有必要去申請新的記憶體空間。相同的事情發生在再次在list中添加兩個元素的時候: L.append(3),L.append(4)。下圖展示了到目前為止我們做了什麼。

Insert

現在我們在列表的第一個位置插入一個整數5:L.insert(1, 5),看看內部發生了什麼。調用了ins1()

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  

虛線框表示已經申請但是沒有使用的記憶體。申請了8個記憶體空間但是list實際用來存儲元素只使用了其中5個記憶體空間
insert的時間複雜度是O(n)

Pop

當你彈出list的最後一個元素：L.pop()。調用listpop()，list_resize在函數listpop()內部被調用，如果這時ob_size（譯者註：彈出元素後）小於allocated（譯者註：已經申請的記憶體空間）的一半。這時申請的記憶體空間將會縮小。

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的時間複雜度是O(1)

你可以發現4號記憶體空間指向還指向那個數值（譯者註：彈出去的那個數值），但是很重要的是ob_size現在卻成了4.
讓我們再彈出一個元素。在list_resize內部，size – 1 = 4 – 1 = 3 比allocated（已經申請的空間）的一半還要小。所以list的申請空間縮小到
6個，list的實際使用空間現在是3個(譯者註：根據(newsize >> 3) + (newsize < 9 ? 3 : 6) = 3在文章最後有詳述)
你可以發現（下圖）3號和4號記憶體空間還存儲著一些整數，但是list的實際使用(存儲元素)空間卻只有3個了。

Remove

Python list對象有一個方法可以移除一個指定的元素。調用listremove()。

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

切開list和刪除元素，調用了list_ass_slice()（譯者註：在上文slice list between element's slot and element's slot + 1被調用），來看下list_ass_slice()是如何工作的。在這裡，低位為1 高位為2（譯者註：傳入的參數），我們移除在1號記憶體空間存儲的數據5

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的時間複雜度為O(n)

譯者註：

文中list的sort部分沒有進行翻譯
核心部分

我們能看到 Python 設計者的苦心。在需要的時候擴容,但又不允許過度的浪費,適當的記憶體回收是非常必要的。
這個確定調整後的空間大小演算法很有意思。
調整後大小 (new_allocated) = 新元素數量 (newsize) + 預留空間 (new_allocated)
調整後的空間肯定能存儲 newsize 個元素。要關註的是預留空間的增長狀況。
將預留演算法改成 Python 版就更清楚了:(newsize // 8) + (newsize < 9 and 3 or 6)。
當 newsize >= allocated,自然按照這個新的長度 "擴容" 記憶體。
而如果 newsize < allocated,且利用率低於一半呢?
allocated    newsize       new_size + new_allocated
10           4             4 + 3
20           9             9 + 7
很顯然,這個新長度小於原來的已分配空間長度,自然會導致 realloc 收縮記憶體。(不容易啊)

引自《深入Python編程》