Python列表和元组的底层实现
有关列表(list)和元组(tuple)的底层实现,本节分别从它们的源码来进行分析。
首先来分析 list 列表,它的具体结构如下所示:
需要注意的是,allocated 和列表的实际空间大小不同,列表实际空间大小,指的是 len(list) 返回的结果,也就是上边代码中注释中的 ob_size,表示该列表总共存储了多少个元素。而在实际情况中,为了优化存储结构,避免每次增加元素都要重新分配内存,列表预分配的空间 allocated 往往会大于 ob_size。
因此 allocated 和 ob_size 的关系是:
如果当前列表分配的空间已满(即 allocated == len(list)),则会向系统请求更大的内存空间,并把原来的元素全部拷贝过去。
接下来再分析元组,如下所示为 Python 3.7 tuple 元组的具体结构:
举个例子,为了提高效率,避免频繁的调用系统函数 free 和 malloc 向操作系统申请和释放空间,tuple 源文件中定义了一个 free_list:
首先来分析 list 列表,它的具体结构如下所示:
typedef struct { PyObject_VAR_HEAD /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */ PyObject **ob_item; /* ob_item contains space for 'allocated' elements. The number * currently in use is ob_size. * Invariants: * 0 <= ob_size <= allocated * len(list) == ob_size * ob_item == NULL implies ob_size == allocated == 0 * list.sort() temporarily sets allocated to -1 to detect mutations. * * Items must normally not be NULL, except during construction when * the list is not yet visible outside the function that builds it. */ Py_ssize_t allocated; } PyListObject;
list 本质上是一个长度可变的连续数组。其中 ob_item 是一个指针列表,里边的每一个指针都指向列表中的元素,而 allocated 则用于存储该列表目前已被分配的空间大小。有兴趣的读者,可直接阅读 list 列表实现的源码文件 listobject.h 和 listobject.c。
需要注意的是,allocated 和列表的实际空间大小不同,列表实际空间大小,指的是 len(list) 返回的结果,也就是上边代码中注释中的 ob_size,表示该列表总共存储了多少个元素。而在实际情况中,为了优化存储结构,避免每次增加元素都要重新分配内存,列表预分配的空间 allocated 往往会大于 ob_size。
因此 allocated 和 ob_size 的关系是:
allocated >= len(list) = ob_size >= 0
。如果当前列表分配的空间已满(即 allocated == len(list)),则会向系统请求更大的内存空间,并把原来的元素全部拷贝过去。
接下来再分析元组,如下所示为 Python 3.7 tuple 元组的具体结构:
typedef struct { PyObject_VAR_HEAD PyObject *ob_item[1]; /* ob_item contains space for 'ob_size' elements. * Items must normally not be NULL, except during construction when * the tuple is not yet visible outside the function that builds it. */ } PyTupleObject;
tuple 和 list 相似,本质也是一个数组,但是空间大小固定。不同于一般数组,Python 的 tuple 做了许多优化,来提升在程序中的效率。有兴趣的读者,可阅读 tuple 元组实现的源码文件 tupleobject.h 和 tupleobject.c。
举个例子,为了提高效率,避免频繁的调用系统函数 free 和 malloc 向操作系统申请和释放空间,tuple 源文件中定义了一个 free_list:
static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];
所有申请过的,小于一定大小的元组,在释放的时候会被放进这个 free_list 中以供下次使用。也就是说,如果以后需要再去创建同样的 tuple,Python 就可以直接从缓存中载入。所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频