有关列表（list）和元组（tuple）的底层实现，本节分别从它们的源码来进行分析。
首先来分析 list 列表，它的具体结构如下所示：
<pre class="python sh_python snippet-formatted sh_sourceCode">
1. typedef struct {
2. PyObject_VAR_HEAD
3. /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
4. PyObject **ob_item;
6. /* ob_item contains space for 'allocated' elements. The number
7. * currently in use is ob_size.
8. * Invariants:
9. * 0 <= ob_size <= allocated
10. * len(list) == ob_size
11. * ob_item == NULL implies ob_size == allocated == 0
12. * list.sort() temporarily sets allocated to -1 to detect mutations.
13. *
14. * Items must normally not be NULL, except during construction when
15. * the list is not yet visible outside the function that builds it.
16. */
17. Py_ssize_t allocated;
18. } PyListObject;
有兴趣的读者，可直接阅读 list 列表实现的源码文件 listobject.h 和 listobject.c。
list 本质上是一个长度可变的连续数组。其中 ob_item 是一个指针列表，里边的每一个指针都指向列表中的元素，而 allocated 则用于存储该列表目前已被分配的空间大小。
需要注意的是，allocated 和列表的实际空间大小不同，列表实际空间大小，指的是 len(list) 返回的结果，也就是上边代码中注释中的 ob_size，表示该列表总共存储了多少个元素。而在实际情况中，为了优化存储结构，避免每次增加元素都要重新分配内存，列表预分配的空间 allocated 往往会大于 ob_size。
因此 allocated 和 ob_size 的关系是：allocated >= len(list) = ob_size >= 0。
如果当前列表分配的空间已满（即 allocated == len(list)），则会向系统请求更大的内存空间，并把原来的元素全部拷贝过去。
接下来再分析元组，如下所示为 Python 3.7 tuple 元组的具体结构：
1. typedef struct {
2. PyObject_VAR_HEAD
3. PyObject *ob_item[1];
5. /* ob_item contains space for 'ob_size' elements.
6. * Items must normally not be NULL, except during construction when
7. * the tuple is not yet visible outside the function that builds it.
8. */
9. } PyTupleObject;
有兴趣的读者，可阅读 tuple 元组实现的源码文件 tupleobject.h 和 tupleobject.c。
tuple 和 list 相似，本质也是一个数组，但是空间大小固定。不同于一般数组，Python 的 tuple 做了许多优化，来提升在程序中的效率。
举个例子，为了提高效率，避免频繁的调用系统函数 free 和 malloc 向操作系统申请和释放空间，tuple 源文件中定义了一个 free_list：
static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];
所有申请过的，小于一定大小的元组，在释放的时候会被放进这个 free_list 中以供下次使用。也就是说，如果以后需要再去创建同样的 tuple，Python 就可以直接从缓存中载入。
笔记来源C语言中文网 http://c.biancheng.net/view/4186.html
网友评论