python學習筆記 --- python中list的實現

dongfangyiyu 發布于2019-07-30 14:19 / 468人閱讀

摘要：中的實現先掛個英文版的原文鏈接這個作者還是可以的，我又發現了他的另外一篇關于的實現，后面的博文再進行介紹。存儲了一系列指向數據的指針。虛線方塊代表了沒用到的。切分并移除元素也就是上面代碼中的，會調用。

python中list的實現

Author : Jasper Yang

School : Bupt

先掛個英文版的原文鏈接 Laurent Luce"s Blog 這個作者還是可以的，我又發現了他的另外一篇關于dict的實現，后面的博文再進行介紹。

在python中實現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 object C structure

一個list對象在 CPython 中是以如下的數據結構保存的。ob_item存儲了一系列指向數據的指針。allocated里面存儲的是該list在內存分配的大小（slots）

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

List initialization

看看當我們初始化一個list是會發生什么，e.g. 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

很重要的一點，我們需要注意到 allocated slots (內存分配的空間大小)和list的size的區別。list的size和 len(l) 是一樣的。allocated slots的個數就是內存中分配了得slot(可以理解成內存的block)個數。你會很經常看到 allocated 比size還要大。這個是為了避免多次的重新分配內存空間（realloc c函數），后面我們會介紹更多。

Append

我們往list里append數據后會發生什么呢~？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()。它超量地分配了比所需的內存更多的內存空間。

增長模式如下：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

現在有4個slot分配給了這個list去存儲指針，你可以看到l[0]指向了我們剛剛append進去的整數對象。虛線方塊代表了沒用到的slot。

We continue by adding one more element: l.append(2). list_resize is called with n+1 = 2 but because the allocated size is 4, there is no need to allocate more memory. Same thing happens when we add 2 more integers: l.append(3), l.append(4). The following diagram shows what we have so far.

我們繼續append更多元素：l.append(2)。list_resize() 被調用了，n = n + 1。但是因為n還是小于 allocated = 4 ，所以沒有必要去重新分配內存空間，同樣的我們繼續append 3 和 4。結果不變。

Insert

讓我們在位置1的地方插入整數5： l.insert(1,5)，ins1() 會被調用。

現在分配的內存slot個數變成了8，這個增長的規律和我們之前講的一模一樣。

Pop

當我們使用彈出：l.pop()，listpop()會被調用，并且如果list的size小于allocated的一半時，list會收縮，也就是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

你可以看到slot 4 仍然指向了原來的整數區域，但是list的size已經縮小了，也就是slot4已經不屬于這個list了。

當我們再pop一次后發現，size已經小于allocated的一半了，于是allocated變成了6。

Remove

python 的 list 還有個特殊的移除元素的方法：l.remove(5) ，這里移除的不是第5個slot而是那個指向的值是5的slot。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并移除元素（也就是上面代碼中的slice），會調用list_ass_slice()。過程如下。

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

希望你們能從我翻譯的這篇文章中學到東西，提高自己~

paper done 2017/04/21

GPU云服務器云服務器 Python學習筆記 python黑客筆記 python語法筆記 python的學習

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/40630.html

python學習筆記－函數的參數

摘要：默認參數的坑默認參數的默認值指向的必需時不變對象。舉一個例說明當函數的默認參數默認為一個可變對象時，會出現什么狀況。例如調用函數輸出結果當然，如果已經又一個對象，也可以在傳入時的名前輸入，會自動將拆分成關鍵字參數。函數就像是一個黑盒子，我們將相關的一些功能打包成一個函數，后續再調用的時候，我們不再關心內部如何實現，而是只關心這個函數需要輸入(Input)什么，需要輸出(Output)...

jasperyang 2019-07-31 10:52 評論0 收藏0
python學習筆記 --- python中的list和numpy中的矩陣分析

摘要：中的和中的矩陣分析由于之前在做的源碼學習，并且將其的源碼翻譯成了的版本。在逛知乎里，我又發現了很多關于為什么這么快的討論，很有意思。作者鏈接來源知乎著作權歸作者所有。 python中的list和numpy中的矩陣分析 Author : Jasper Yang School : Bupt preface 由于之前在做GIbbsLDA++的源碼學習，并且將其c++的源碼翻譯成了pyth...

DobbyKim 2019-07-30 14:18 評論0 收藏0
python 學習筆記關于切片

摘要：我們還可以給切片進行命名，有名字的切片，顯然更具有可讀性。對切片賦值時，賦值符號右側必須是一個可迭代對象，即使這個對象只包含一個元素，否則會提示錯誤。注以上內容主體來自于流暢的一書中切片和切片原理切片是python中列表（list）、元組（tuple）、字符串（str）等序列類型都支持的一種操作，但實際上切片的功能比人們所想象的要強大的多。切片區間為什么會忽略最后一個元素當只有...

jerryloveemily 2019-07-30 17:17 評論0 收藏0
Python學習筆記2（解釋器+運算符）

摘要：解釋器的系統上，一般默認的版本為，我們可以將安裝在目錄中。中的按位運算法則如下下表中變量為，為，二進制格式如下邏輯運算符圖片邏輯運算符測試實例中包含了一系列的成員，包括字符串，列表或元組。 3.Python3解釋器 Linux/Unix的系統上，一般默認的 python 版本為 2.x，我們可以將 python3.x 安裝在 /usr/local/python3 目錄中。安裝完成后，...

happyhuangjinjin 2019-07-30 17:18 評論0 收藏0
python學習筆記序列

內置序列容器序列 list, tuple, collections.deque等這些序列能存放不同類型的數據扁平序列 str, byte, bytearray, memoryview, array.array, 這些序列只能容納一種類型數據以上，容器序列存放的是他們所含任意類型對象的引用，而扁平序列存放的是值而不是引用列表（list）是最基礎也是最重要的序列類型列表推導 >>> symb...

godiscoder 2019-07-30 17:20 評論0 收藏0