首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >软件测试 | Python 中 list 的底层实现方式

软件测试 | Python 中 list 的底层实现方式

原创
作者头像
霍格沃兹测试开发
修改2021-03-22 17:49:45
5390
修改2021-03-22 17:49:45
举报
文章被收录于专栏:测吧测试开发测吧测试开发

本篇文章描述了 CPython 中 list 的实现方式。原文链接:https://ceshiren.com/t/topic/10916

C 语言用结构体表示 List 对象

C 语言使用结构体实现 list 对象,结构体代码如下。

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item; //指向 list 中的对象
    Py_ssize_t allocated; //内存分配的插槽
} PyListObject;

List 初始化

I = [] 为例

list 的数量是指 len(l)。分配的槽位数量是指在内存中实际分配的数量。通常情况,内存中分配的数量要大于 list 的数量。这是为了当添加新元素时,避免内存再分配。

Append

当运行l.append(1)时, CPython 将调用app1()

在这里插入图片描述
在这里插入图片描述

list_resize() 会故意分配更多的内存,避免被多次调用。分配内存大小增加:0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...

在这里插入图片描述
在这里插入图片描述

第一次分配了 4 个槽位,I[0] 指向了数字对象 1 。正方形虚线表示未使用过的槽位。追加操作的均摊复杂度为 O(1) 。

均摊时间复杂度是平均时间复杂度的一种,是一种简化的计算方法。

在这里插入图片描述
在这里插入图片描述

继续追加元素:l.append(2)。调用 list_resize 实现 n + 1 = 2。由于分配了四个空间,不需要分配内存。当再向列表追加两个数字时,l.append(3), l.append(4),如下图如示:

在这里插入图片描述
在这里插入图片描述

Insert

在位置 1 插入整型 5 ,即调用 python 的 l.insert(1, 5) 。CPython 会调用 ins1()

在这里插入图片描述
在这里插入图片描述

插入操作需要将剩余元素向右迁移:

在这里插入图片描述
在这里插入图片描述

上图虚线表示未使用的槽位(slots),分配了 8 个槽位,但 list 的长度只有 5 。 insert 的时间复杂度为 O(n)。

pop

弹出列表的最后一个元素使用 l.pop(),CPython 使用 listpop() 实现这个过程。如果新内存大小少于分配大小的一半, listpop() 将调用 list_resize 减少 list 内存。

在这里插入图片描述
在这里插入图片描述

Pop 的时间复杂度是 O(1)。

在这里插入图片描述
在这里插入图片描述

注意,此时槽位 4 仍然指向整型 4 ,但是 list 的大小却是 4 。只有 pop 更多的元素才能调用 list_resize() 减少内存,如果再 pop 一个元素, size - 1 = 4 - 3 = 3, 3 小于分配槽位的一半 8/2 = 4 。所以 list 收缩到 6 个槽位, list 的大小为 3 。虽然槽位 3 和 4 依旧指向整型对象,但是整体大小变成了 3 。

在这里插入图片描述
在这里插入图片描述

remove

Python 可以用 remove 删除指定元素:l.remove(5)。此时将调用 listremove()

在这里插入图片描述
在这里插入图片描述

CPython 调用 list_ass_slice() 函数对列表进行切分并删除元素。当在位置 1 移除元素 5 时,低偏移(low offset)是 1 ,高偏移(high offset)是 2 :

在这里插入图片描述
在这里插入图片描述

remove 时间复杂度是 O(n)。

在这里插入图片描述
在这里插入图片描述

文章参考:http://www.laurentluce.com/posts/python-list-implementation/

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • C 语言用结构体表示 List 对象
  • List 初始化
  • Append
  • Insert
  • pop
  • remove
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档