【Python】元组和列表的区别、底层实现

缺乏、安全感 2022-10-11 13:53 204阅读 0赞

### 元组和列表的区别、底层实现 ###

*  概述
 *  元组和列表有哪些区别呢？
 *  列表和元组的底层实现

# 概述 #

`元组`和`列表`同属`序列类型`，且都可以按照特定顺序存放一组数据，数据类型不受限制，只要是 Python 支持的数据类型就可以。

# 元组和列表有哪些区别呢？ #

元组和列表最大的区别就是，列表中的元素可以进行任意修改，就好比是用铅笔在纸上写的字，写错了还可以擦除重写；

而元组中的元素无法修改，除非将元组整体替换掉，就好比是用圆珠笔写的字，写了就擦不掉了，除非换一张纸。

> 可以理解为，`tuple 元组`是一个只读版本的 `list 列表`。

需要注意的是，这样的差异势必会影响两者的存储方式，我们来直接看下面的例子：

>>> listdemo = []
    >>> listdemo.__sizeof__()
    40
    >>> tupleDemo = ()
    >>> tupleDemo.__sizeof__()
    24

可以看到，对于列表和元组来说，虽然它们都是空的，但元组却比列表少占用 `16 个字节`，这是为什么呢？

*  事实上，就是由于列表是动态的，它需要存储指针来指向对应的元素（占用 8 个字节）。
 *  另外，由于列表中元素可变，所以需要额外存储已经分配的长度大小（占用 8 个字节）。
 *  但是对于元组，情况就不同了，元组长度大小固定，且存储元素不可变，所以存储空间也是固定的。

既然列表这么强大，还要元组这种序列类型干什么？

通过对比列表和元组存储方式的差异，我们可以引申出这样的结论，即元组要比列表更加轻量级，所以从总体上来说，元组的性能速度要优于列表。

另外，Python 会在后台，对静态数据做一些资源缓存。通常来说，因为垃圾回收机制的存在，如果一些变量不被使用了，Python 就会回收它们所占用的内存，返还给操作系统，以便其他变量或其他应用使用。

但是对于一些静态变量（比如元组），如果它不被使用并且占用空间不大时，Python 会暂时缓存这部分内存。

这样的话，当下次再创建同样大小的元组时，Python 就可以不用再向操作系统发出请求去寻找内存，而是可以直接分配之前缓存的内存空间，这样就能大大加快程序的运行速度。

下面的例子，是计算初始化一个相同元素的`列表`和`元组`分别所需的时间。可以看到，元组的初始化速度要比列表快 5 倍。

C:\Users\qinjl>python -m timeit 'x=(1,2,3,4,5,6)'
    20000000 loops, best of 5: 9.97 nsec per loop
    C:\Users\qinjl>python -m timeit 'x=[1,2,3,4,5,6]'
    5000000 loops, best of 5: 50.1 nsec per loop

> 当然，如果你想要增加、删减或者改变元素，那么列表显然更优。因为对于元组来说，必须得通过新建一个元组来完成。

总的来说，元组确实没有列表那么多功能，但是元组依旧是很重要的序列类型之一，元组的不可替代性体现在以下这些场景中：

*  元组作为很多内置函数和序列类型方法的返回值存在，也就是说，在使用某些函数或者方法时，它的返回值会是元组类型，因此你必须对元组进行处理。
 *  元组比列表的访问和处理速度更快，因此，当需要对指定元素进行访问，且不涉及修改元素的操作时，建议使用元组。
 *  元组可以在映射（和集合的成员）中当做“`键`”使用，而列表不行。

# 列表和元组的底层实现 #

有关`列表（list）`和`元组（tuple）`的底层实现，分别从它们的源码来进行分析。

首先来分析 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 列表`实现的源码文件 [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 元组的具体结构：

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 元组`实现的源码文件 [tupleobject.h][] 和 [tupleobject.c][]。

`tuple` 和 `list` 相似，本质也是一个数组，但是空间大小固定。不同于一般数组，Python 的 tuple 做了许多优化，来提升在程序中的效率。

举个例子，为了提高效率，避免频繁的调用系统函数 `free` 和 `malloc` 向操作系统申请和释放空间，`tuple 源文件`中定义了一个 `free_list`：

static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];

所有申请过的，小于一定大小的元组，在释放的时候会被放进这个 `free_list` 中以供下次使用。也就是说，如果以后需要再去创建同样的 `tuple`，Python 就可以直接从缓存中载入。

[listobject.h]: https://github.com/python/cpython/blob/949fe976d5c62ae63ed505ecf729f815d0baccfc/Include/listobject.h#L23
[listobject.c]: https://github.com/python/cpython/blob/3d75bd15ac82575967db367c517d7e6e703a6de3/Objects/listobject.c#L33
[tupleobject.h]: https://github.com/python/cpython/blob/3d75bd15ac82575967db367c517d7e6e703a6de3/Include/tupleobject.h#L25
[tupleobject.c]: https://github.com/python/cpython/blob/3d75bd15ac82575967db367c517d7e6e703a6de3/Objects/tupleobject.c#L16