python學(xué)習(xí)筆記 --- python中l(wèi)ist的實(shí)現(xiàn)

dongfangyiyu 發(fā)布于2019-07-30 14:19 / 476人閱讀

摘要：中的實(shí)現(xiàn)先掛個(gè)英文版的原文鏈接這個(gè)作者還是可以的，我又發(fā)現(xiàn)了他的另外一篇關(guān)于的實(shí)現(xiàn)，后面的博文再進(jìn)行介紹。存儲(chǔ)了一系列指向數(shù)據(jù)的指針。虛線方塊代表了沒用到的。切分并移除元素也就是上面代碼中的，會(huì)調(diào)用。

python中l(wèi)ist的實(shí)現(xiàn)

Author : Jasper Yang

School : Bupt

先掛個(gè)英文版的原文鏈接 Laurent Luce"s Blog 這個(gè)作者還是可以的，我又發(fā)現(xiàn)了他的另外一篇關(guān)于dict的實(shí)現(xiàn)，后面的博文再進(jìn)行介紹。

在python中實(shí)現(xiàn)list是十分有趣的事情，list在現(xiàn)實(shí)使用中是那么的強(qiáng)大而令人喜愛，所以，下面讓我們一起來(lái)一探究竟。

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

一個(gè)list對(duì)象在 CPython 中是以如下的數(shù)據(jù)結(jié)構(gòu)保存的。ob_item存儲(chǔ)了一系列指向數(shù)據(jù)的指針。allocated里面存儲(chǔ)的是該list在內(nèi)存分配的大小（slots）

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

List initialization

看看當(dāng)我們初始化一個(gè)list是會(huì)發(fā)生什么，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

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

Append

我們往list里append數(shù)據(jù)后會(huì)發(fā)生什么呢~？c的內(nèi)置函數(shù) app1()會(huì)被調(diào)用。

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

讓我們來(lái)看看這個(gè)list_resize()。它超量地分配了比所需的內(nèi)存更多的內(nèi)存空間。

增長(zhǎng)模式如下：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è)slot分配給了這個(gè)list去存儲(chǔ)指針，你可以看到l[0]指向了我們剛剛append進(jìn)去的整數(shù)對(duì)象。虛線方塊代表了沒用到的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.

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

Insert

讓我們?cè)谖恢?的地方插入整數(shù)5： l.insert(1,5)，ins1() 會(huì)被調(diào)用。

現(xiàn)在分配的內(nèi)存slot個(gè)數(shù)變成了8，這個(gè)增長(zhǎng)的規(guī)律和我們之前講的一模一樣。

Pop

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

你可以看到slot 4 仍然指向了原來(lái)的整數(shù)區(qū)域，但是list的size已經(jīng)縮小了，也就是slot4已經(jīng)不屬于這個(gè)list了。

當(dāng)我們?cè)賞op一次后發(fā)現(xiàn)，size已經(jīng)小于allocated的一半了，于是allocated變成了6。

Remove

python 的 list 還有個(gè)特殊的移除元素的方法：l.remove(5) ，這里移除的不是第5個(gè)slot而是那個(gè)指向的值是5的slot。listremove() 會(huì)被調(diào)用。

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），會(huì)調(diào)用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

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