如何深入Python列表的内部实现

发布时间:2021-10-26 17:13:28 作者:柒染
来源:亿速云 阅读:189

这篇文章给大家介绍如何深入Python列表的内部实现,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。

Python 中的列表非常强大,看看它的内部实现机制是怎么样的,一定非常有趣。

下面是一段 Python 脚本,在列表中添加几个整数,然后打印列表。

>>> l = []  >>> l.append(1)  >>> l.append(2)  >>> l.append(3)  >>> l  [1, 2, 3]  >>> for e in l:  ...   print e  ...  1  2  3

可以发现,列表是一个迭代器。

列表对象的 C 语言结构体

Cpython 中的列表实现类似于下面的 C 结构体。ob_item 是指向列表对象的指针数组。allocated 是申请内存的槽的个数。

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

列表初始化

看看初始化一个空列表的时候发生了什么,例如: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

要分清列表大小和分配的槽大小,这很重要。列表的大小和 len(l)  的大小相同。分配槽的大小是指已经在内存中分配了的槽空间数。通常分配的槽的大小要大于列表大小,这是为了避免每次列表添加元素的时候都调用分配内存的函数。下面会具体介绍。

Append 操作

向列表添加一个整数:l.append(1) 时发生了什么?调用了底层的 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

现在分配了 4 个用来装列表元素的槽空间,并且***个空间中为整数 1。如下图显示 l[0]  指向我们新添加的整数对象。虚线的方框表示已经分配但没有使用的槽空间。

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

如何深入Python列表的内部实现

继续添加新的元素:l.append(2)。调用 list_resize 函数,参数为 n+1 = 2, 但是因为已经申请了 4  个槽空间,所以不需要再申请内存空间。再添加两个整数的情况也是一样的:l.append(3),l.append(4)。下图显示了我们现在的情况。 

如何深入Python列表的内部实现

Insert 操作

在列表偏移量 1 的位置插入新元素,整数 5:l.insert(1,5),内部调用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

如何深入Python列表的内部实现

虚线的方框依旧表示已经分配但没有使用的槽空间。现在分配了 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 is not less than 8/2 so no shrinkage      set list object size to 4      return last element

列表 pop 操作的平均复杂度为 O(1)。

如何深入Python列表的内部实现

可以看到 pop 操作后槽空间 4 依然指向原先的整数对象,但是最为关键的是现在列表的大小已经变为 4。

继续 pop 一个元素。在 list_resize() 函数中,size &ndash; 1 = 4 &ndash; 1 = 3  已经小于所分配的槽空间大小的一半,所以缩减分配的槽空间为 6,同时现在列表的大小为 3。

可以看到槽空间 3 和 4 依然指向原先的整数,但是现在列表的大小已经变为 3。

如何深入Python列表的内部实现

Remove 操作

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() 函数,它的实现方法比较有趣。我们在删除列表位置 1 的元素 5  的时候,低位的偏移量为 1 同时高位的偏移量为 2.

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

列表 remove 操作的复杂度为 O(n)。

如何深入Python列表的内部实现

关于如何深入Python列表的内部实现就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。

推荐阅读:
  1. 自定义RPC的完整实现---深入理解rpc内部原理
  2. HashMap的内部实现

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

python

上一篇:MySQL数据库如何选择

下一篇:Word流程图如何画

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》