深入Python列表的内部实现

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

如今分派了 4 个用来装列表元素的槽空间，并且第一个空间中为整数 1。如下图显示 l[0] 指向我们新添加的┞符数对象。虚线的方框表示已经分派但没有应用的槽空间。

列表追加元素操作的平均复杂度为 O(1)。

持续添加新的元素：l.append(2)。调用 list_resize 函数，参数为 n+1 = 2，然则因为已经申请了 4 个槽空间，所以不须要再申请内存空间。再添加两个整数的情况也是一样的：l.append(3)，l.append(4)。下图显示了我们如今的情况。

本文将介绍列表在 CPython中的实现，因为毕竟Cpython 又是 Python 最为常用的实现。

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 个槽空间，然则列表的大年夜小却只是 5。

列表插入操作的平均复杂度为 O(n)。

Pop 操作

掏出列表最后一个元素即l.pop()，调用了 listpop() 函数。在 listpop() 函数中会调用 list_resize 函数，如不雅掏出元素后列表的大年夜小小于分派的槽空间数的一半，将会缩减列表的大年夜小。

arguments: list object 
 
returns: element popped 
 
listpop: 
 
    if list empty: 
 
        return null 
 
    resize list with size 5 - 1 = 4. 4 	
			 2/4   首页 上一页 1 2 3 4 下一页 尾页	
			

　　推荐阅读
　　Python爬虫爬取知乎小结
            
            比来进修了一点收集爬虫，并实现了应用Python来爬取知乎的一些功能，这里做一个小的总结。收集爬虫是指经由过程必定的规矩主动的大年夜网上抓取一些信息的法度榜样或脚本。我们知道机械进>>>详细阅读


本文标题：深入Python列表的内部实现
地址：http://www.17bianji.com/lsqh/35408.html
 1/2    1