Python 列表实现

原文：http://www.laurentluce.com/posts/python-list-implementation/

本文是翻译。

slot 只译插槽 本文中存放元素的预留位置

这篇文章描述了在CPython中实现的list对象，CPython解释器是最常用的Python语言实现。
列表在Python中是非常强大的，我们看它内部实现会发现很有趣。
下面是一个简单的Python脚本，添加及格整数到一个列表，并且打印它们。

list实现01.png

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

List对象的C结构

List对象在CPython中使用以下C结构体表示。ob_item是指向List元素的指针。allocated是分配的实际的内存插槽数量。
(注：list[0]就是ob_item[0], allocated是内存分配的大小，不是实际元素多少，实际元素数量存储在VAR_HEAD中。TIP：）

list实现02.png

List初始化

我们来看一下初始化一个空的列表会发生什么

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)是一样的，分配的插槽数量就是在内存中分配的数量。通常，你会看到allocated会大于size。这样避免了在每次添加元素的时候重新分配内存，我们会稍会进行详细介绍

追加元素

我们添加一个整数到一个列表：l.append(1) 。会发生什么呢？CPython内部的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太多次。列表增长的模式是： 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

现在分配了四个插槽来装元素，第一个元素是整数1，你可以看到下面的图中的 l[0]指向的一个整数就是我们刚才追加的。虚线方格就是代表了插槽已经分配但是没有被使用。

追加操作的平均复杂度是 O(1)

list实现03.png

我们继续添加更多的元素: l.append(2), list_resize的new_size: n+1 = 2, allocated的大小是4，所以这个时候是不会去分配内存的。当我们多添加两个整数， l.append(3), l.append(4)，也是不会分配的。下图显示了到目前为止的内容。

list实现04.png

插入元素

现在在第一个位置插入一个整数5，l.insert(15) ，然后看看内部会发生什么。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

list实现05.png

虚线框框代表了插槽分配了但是没有被使用。上图，8个插槽分配了，但是列表的长度只有5。
插入操作的复杂度为O(n)。

弹出元素

当你弹出一个元素：l.pop(), listpop会调用。如果新的列表大小小于一半分配的插槽大小那么就会缩小插槽并且会调用list_resize()

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)

list实现06.png

你可以观察到插槽4仍然指向那个整数，更重要的是，现在列表的大小是4
让我们弹出更多的元素, list_resize(), size – 1 = 4 – 1 = 3 现在小于分配的插槽数量的一半，所以现在列表缩小到6个插槽大小，并且新的列表的大小现在为3。
你可以观察到插槽3和插槽4现在仍然指向一些整数，重要的是现在列表的大小变为了3。

list实现07.png

移除元素

Python 列表对象有一个方法指定移除一个元素：l.remove(5). 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会调用，Here, low offset is 1 and high offset is 2 as we are removing the element 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

删除操作的复杂度是O(n)

list实现07.png