Python list 实现

电玩女神 2022-10-29 03:15 158阅读 0赞

## List 对象的C结构 ##

CPython 中的列表对象由以下 C 结构表示。ob\_item是指向列表元素的指针列表。分配的是内存中分配的插槽数。

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

## 初始化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

注意分配的slot和size是不同的，这个size就是len(), 分配的slot其实就是内存大小。所以经常看到分配的是大于这个size的，因为避免每次追加的时候都重新分配内存。

## append 功能 ##

append一个整数到list里面, l.append(1)

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

上面有4个slot被分配来扩容，只有第一个l\[0\]指向了刚刚追加的元素。虚线下面的表示分配了没有使用。  
可以看出时间复杂度是o(1)

![1][]

既然有分配多的空间，那就继续append更多的值。

![1][1 1]

## insert 功能 ##

在1的位置插入一个数字l.insert(1,5)

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个slots，但是只有5个长度，看到时间复杂度是O(n)

![3][]

## pop 功能 ##

默认移除最后一个元素，并返回该值。  
如果list的pop移除后的大小 小于 分配的一半的话，这个list就减少。  
下面刚好是一半，不小于，所以分配大小不变  
时间复杂度是O(1)

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

![4][]

如果再移除一个元素就小于一半了，则分配大小就是减少后的大小的一半。所以分配大小就是6 slots  
可以看到 位置3和4仍然是指向空的。

![5][]

## remove 功能 ##

指定元素移除。l.remove(1), 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\_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

![6][]

remove的时间负责度是O(n)。

## readmore ##

[https://docs.python.org/3/c-api/list.html][https_docs.python.org_3_c-api_list.html]

[http://www.laurentluce.com/posts/python-list-implementation/][http_www.laurentluce.com_posts_python-list-implementation]

[1]: /images/20221024/7e0e8f3ac12943a48f8b0957c08ae23e.png
[1 1]: /images/20221024/3ad0513a23894ef68089770d2e270d60.png
[3]: /images/20221024/72861ea1f7e04641aa021cd8ec820670.png
[4]: /images/20221024/9a59080ba2f84066bd301efc81bb1602.png
[5]: /images/20221024/4f894b80c74c427b8f424cee059a4542.png
[6]: /images/20221024/dc5da164867049ec9001339cbc5b4dd7.png
[https_docs.python.org_3_c-api_list.html]: https://docs.python.org/3/c-api/list.html
[http_www.laurentluce.com_posts_python-list-implementation]: http://www.laurentluce.com/posts/python-list-implementation/