2023年7月26日发(作者：)

pythonlist底层数据结构_深⼊Python数据结构（⼀）——list1. 前⾔列表是Python中最基本的数据结构。类似于数据结构中的⼴义表[?]。列表是最常⽤的Python数据类型，它可以作为⼀个⽅括号内的逗号分隔值出现。创建⼀个列表，只要把逗号分隔的不同的数据项使⽤⽅括号括起来即可list1 = [1, 2, 3]列表的数据项不需要具有相同的类型,甚⾄另⼀个列表也可以是列表的⼀个数据项list2 = ['a', 'b', [1, 2, 3] ]list3 = [1, 2, list1]2. 使⽤列表都可以进⾏的操作包括索引，切⽚，添加，删除，检查成员，复制、排序、扩展等操作。如果你还不熟悉Python的列表 >>> Python 列表(List) | 菜鸟教程list常见⽅法2.1 count()统计列表中某⼀项出现的次数>>> list1 = [1,2,3]>>> (2)12.2 append()向列表末尾添加⼀个object>>> list1 = [1,2,3]>>> (4)>>> list1[1, 2, 3, 4]2.3 index()获取某⼀个object在list中第⼀次出现的下标, 当不存在该object时会报错,产⽣⼀个ValueError异常>>> (4)3>>> (-1)Traceback (most recent call last):File "", line 1, inValueError: -1 is not in list# 检查某⼀范围内是否有某object,有则返回该object的下标>>>2.4 sort()对列表内元素按照⼀定规则排序# 默认升序>>> list2 = [1,3,5,2,4,6]>>> ()>>> list2[1, 2, 3, 4, 5, 6]# 通过sort()⽅法⽣成降序>>> (reverse=True)>>> list2[6, 5, 4, 3, 2, 1]# ⾃定义排序⽅法 (根据字符的ascii码⼤⼩排序>>> list3 = ['a', 'b', 'C', '0', 'A']>>> (cmp=lambda x, y: 1 if ord(x) >= ord(y) else -1)>>> list3['0', 'A', 'C', 'a', 'b']值得⼀提的是 这⾥的底层所使⽤的排序⽅法python中⽐较常见的timsort(可以视为归并排序的改进版本,对于较⼩的数据块采⽤插⼊排序.然后合并每个有序部分,是⼀个平均时间复杂度为O(nlogn),空间复杂度O(n) 的稳定排序算法)更多有关Timsort的内容 >>> Timsort原理介绍Python有关list排序的官⽅⽂档 listsort2.5 extend()扩展列表,将extend中可迭代对象的每⼀个元素依次放⼊之前列表的后⽅>>> list1[1, 2, 3, 4]>>> list2[6, 5, 4, 3, 2, 1]>>> (list2)>>> list1[1, 2, 3, 4, 6, 5, 4, 3, 2, 1]2.6 insert()在列表指定位置插⼊元素>>> list1 = [1,2,3]>>> (0,-1)>>> list1[-1, 1, 2, 3]>>> (1,10)>>> list1[-1, 10, 1, 2, 3]2.7 pop()弹出列表指定位置的元素,并且返回这个元素>>> list1 = [1,2,3]>>> ()3>>> list1[1, 2]>>> (1)2>>> list1[1]2.8 remove()移除列表第⼀次出现的某个object>>> list1 = [1,2,3,3,4,5]>>> (3)>>> list1[1, 2, 3, 4, 5]2.9 reverse()反序⼀个列表>>> list1 = [1,2,3,4,5]>>> e()>>> list1[5, 4, 3, 2, 1]2.10 in检测⼀个object是否在列表中>>> list1 = [1,2,3]>>> 1 in list1True>>> 0 in list1False2.11 max(), min()获取列表中元素的最⼤,最⼩值>>> list1[1, 2, 3]>>> min(list1)1>>> max(list1)32.12 len()获取列表长度(列表中若有嵌套列表,不论其多长也只会被计算为1)>>> list2 = [1,2,[1,2,3,4,5]]>>> len(list2)3len() 其实是⼀个⽐较神奇的⽅法,它是由Cpython直接调⽤python对象结构体中的计数变量所得到的结果.速度⾮常快 时间复杂度是O(1)3. 分析Python官⽅⽂档中写道Internally, a list is represented as an array;the largest costs come from growing beyond the current allocation size (because everything must move), or from insertingor deleting somewhere near the beginning (because everything after that must move). If you need to add/remove at bothends, consider using a instead.简单翻译⼀下:list内部是通过数组实现的,其最⼤的时间开销在于:长度超过了默认的最⼤长度,需要扩展长度的时候(原列表的每⼀项都要被移动)在列表靠近开始的地⽅进⾏插⼊或者删除操作.(插⼊或者删除位置之后的每⼀项元素都要被移动)如果你需要频繁的插⼊或者删除头尾部分的元素,考虑去使⽤ (双端队列) 代替list各个⽅法的时间复杂度list各个⽅法的时间复杂度可以看到在尾部插⼊,获取和修改元素 时间复杂度都是O(1)⽽在其他部分插⼊元素,删除都是O(n),⽐较符合数组的时间复杂度特征底层实现最后我们关⼼⼀下list的底层实现⽅式,就可以更好的理解列表之前所分析的各个⽅法的时间复杂度.由于Python最主流的解释器还是CPython,下⾯介绍⼀下CPython的内部实现.3.1 列表对象的 C 语⾔结构体Cpython 中的列表实现类似于下⾯的 C 结构体。ob_item 是指向列表对象的指针数组。allocated 是申请内存的槽的个数。typedef struct {PyObject_VAR_HEADPyObject **ob_item;Py_ssize_t allocated;} PyListObject;3.2 列表初始化看看初始化⼀个空列表的时候发⽣了什么，例如：l = []。arguments: size of the list = 0returns: list object = []PyListNew:nbytes = size * size of global Python object = 0allocate new list objectallocate list of pointers (ob_item) of size nbytes = 0clear ob_itemset list's allocated var to 0 = 0 slotsreturn list object要分清列表⼤⼩和分配的槽⼤⼩，这很重要。列表的⼤⼩和 len(l) 的⼤⼩相同。分配槽的⼤⼩是指已经在内存中分配了的槽空间数。通常分配的槽的⼤⼩要⼤于列表⼤⼩，这是为了避免每次列表添加元素的时候都调⽤分配内存的函数。下⾯会具体介绍。3.3 Append 操作向列表添加⼀个整数：(1) 时发⽣了什么？调⽤了底层的 C 函数 app1()。arguments: list object, new elementreturns: 0 if OK, -1 if notapp1:n = size of listcall list_resize() to resize the list to size n+1 = 0 + 1 = 1list[n] = list[0] = new elementreturn 0下⾯是 list_resize() 函数。它会多申请⼀些内存，避免频繁调⽤ list_resize() 函数。列表的增长模式为：0，4，8，16，25，35，46，58，72，88……arguments: list object, new sizereturns: 0 if OK, -1 if notlist_resize:new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) = 3new_allocated += newsize = 3 + 1 = 4resize ob_item (list of pointers) to size new_allocatedreturn 0现在分配了 4 个⽤来装列表元素的槽空间，并且第⼀个空间中为整数 1。如下图显⽰ l[0] 指向我们新添加的整数对象。虚线的⽅框表⽰已经分配但没有使⽤的槽空间。列表追加元素操作的平均复杂度为 O(1)。继续添加新的元素：(2)。调⽤ list_resize 函数，参数为 n+1 = 2， 但是因为已经申请了 4 个槽空间，所以不需要再申请内存空间。再添加两个整数的情况也是⼀样的：(3)，(4)。下图显⽰了我们现在的情况。3.4 Insert 操作在列表偏移量 1 的位置插⼊新元素，整数 5：(1,5)，内部调⽤ins1() 函数。arguments: list object, where, new elementreturns: 0 if OK, -1 if notins1:resize list to size n+1 = 5 -> 4 more slots will be allocatedstarting at the last element up to the offset where, right shift each elementset new element at offset wherereturn 0虚线的⽅框依旧表⽰已经分配但没有使⽤的槽空间。现在分配了 8 个槽空间，但是列表的⼤⼩却只是 5。列表插⼊操作的平均复杂度为 O(n)。3.5 Pop 操作取出列表最后⼀个元素 即()，调⽤了 listpop() 函数。在 listpop() 函数中会调⽤ list_resize 函数，如果取出元素后列表的⼤⼩⼩于分配的槽空间数的⼀半，将会缩减列表的⼤⼩。arguments: list objectreturns: element poppedlistpop:if list empty:return nullresize list with size 5 - 1 = 4. 4 is not less than 8/2 so no shrinkageset list object size to 4return last element列表 pop 操作(pop-last)的平均复杂度为 O(1) 。可以看到 pop 操作后槽空间 4 依然指向原先的整数对象，但是最为关键的是现在列表的⼤⼩已经变为 4。继续 pop ⼀个元素。在 list_resize() 函数中，size – 1 = 4 – 1 = 3 已经⼩于所分配的槽空间⼤⼩的⼀半，所以缩减分配的槽空间为6，同时现在列表的⼤⼩为 3。可以看到槽空间 3 和 4 依然指向原先的整数，但是现在列表的⼤⼩已经变为 3。3.6 Remove 操作Python 的列表对象有个⽅法，删除指定的元素： (5)。底层调⽤ listremove() 函数。arguments: list object, element to removereturns none if OK, null if notlistremove:loop through each list element:if correct element:slice list between element's slot and element's slot + 1return nonereturn null为了做列表的切⽚并且删除元素，调⽤了 list_ass_slice() 函数，它的实现⽅法⽐较有趣。我们在删除列表位置 1 的元素 5 的时候，低位的偏移量为 1 同时⾼位的偏移量为 nts: list object, low offset, high offsetreturns: 0 if OKlist_ass_slice:copy integer 5 to recycle list to dereference itshift elements from slot 2 to slot 1resize list to 5 slotsreturn 0列表 remove 操作的复杂度为 O(n)。参考⽂献