python学习笔记 --- python中list的实现

dongfangyiyu 发布于2019-07-30 14:19 / 467人阅读

摘要：中的实现先挂个英文版的原文链接这个作者还是可以的，我又发现了他的另外一篇关于的实现，后面的博文再进行介绍。存储了一系列指向数据的指针。虚线方块代表了没用到的。切分并移除元素也就是上面代码中的，会调用。

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的学习

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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