关于Python列表底层实现原理

目录

• 关于Python列表底层实现原理
• • 引言
  • 一、空列表和空元组分别占多少内存空间？
  • 二、为什么列表和元组可以保存不同类型的数据
  • 三、Python列表的扩容机制
  • 四、列表和元组初始化时的共有部分都有哪些内容
  • 五、列表和元组的性能差异

引言

今天学习极客时间上的《Python核心技术与实战》课程，在看了第3课关于列表和元组的深入剖析后，觉得自己以前对于列表元组的理解还不够深入，于是跟着课程中老师提供的思路搜索了资料，算是整理出了一些知识体系吧。

一、空列表和空元组分别占多少内存空间？

课程中，老师以一个例子引出学习内容，这个例子就是我们创建一个空列表和一个空元组，然后观察两者所占内存大小，通过内存差异引出两者实现上的差别。

l = list()
t = tuple()
print(l.__sizeof__())  # 40
print(t.__sizeof__())  # 24

是的，一个空列表在内存中要占40字节，空元组则要占24字节。

我们首先从两者之间相差的这16字节入手。

Python列表为了实现“可变长”这个特性，与元组的“不可变长”就差在这16字节上。这16字节中，包括一个保存列表目前已保存数据量的变量ob_size，在Python解释器中，一个int变量占8字节；而另外8字节则是一个指针变量，该指针变量用来指向列表本身。

那么问题来了，为什么列表需要一个指针记录自己的地址，而元组就不需要呢？

因为列表的可变长特性，要求列表插入或者删除元素都是在原列表上进行操作，所以需要记录列表本身的地址，保证操作的都是同一个列表；而元组不需要保证自己的地址，因为一旦我们想要修改元组，那么只能重新开辟一个新的元组，新的元组有新的地址，旧的地址不需要保存。

好了，到这里大概描述了列表和元组之间相差的16字节具体差了些什么。

二、为什么列表和元组可以保存不同类型的数据

博主科班出身，读大一的时候学习过C、C++、Java等编程语言，拿C语言具体，数组这个数据结构和Python列表有一定的相似性，但是数组只能保存相同类型的数据，在定义数组时，就要规定数组元素的类型，使用时只能保存定义类型的数据（或支持隐式转换的类型）。

那么Python列表和元组究竟是如何支持保存不同类型的数据呢？如果对插入删除的数据类型不做限制，扩容时每次扩容的大小也不确定，好像很难权衡，这次我可能插入一个int型，下次我可能就插入一个布尔型，每次扩容的大小未知。

事实上，Python列表和元组具体存储的都是元素的地址。对于这个概念，我的理解是，列表和元组本质上可以看成是一个指针列表，里面存放了每个元素的地址，而这些地址指向的具体元素，类型和大小可能是不同的，正是这种机制实现了不同数据类型元素的存储。

对于存储的每个指针变量，都占8字节，所以在列表和元组本身看来，每次插入的元素大小都是固定的。

三、Python列表的扩容机制

对于扩容机制，只谈列表，因为元组不可变，想要对元组“扩容”，只能重新开辟一个新元组，并不是严格意义上的扩容。

我们首先观察一段代码：

# 初始化列表后，向列表中新增第一个元素
l = list()
l.__sizeof__()  # 40

l.append(1)
l.__sizeof__()  # 72

l.append(2)
l.__sizeof__()  # 72

光看这部分代码，我们就可以提出两个问题：
1、按照列表存储的是指针这个说法，为什么插入一个元素后，列表大小会从40字节一下子变成72字节呢？
2、当我们第二次插入元素时，列表大小没变，为什么还是72字节？

试想，Python列表保存的是指针，每次插入一个元素都会为列表增大8字节的大小，如果我们每次遇到插入元素的操作都只增大8字节空间，那么列表就要频繁地执行空间分配的操作，时间开销非常大。所以，Python列表采用的是“过度分配”机制（over-allocating），当列表空间满时，如果再遇到元素插入，则不仅仅分配新元素大小的空间，而是多分配一部分空间，避免之后几次插入操作还要执行空间分配，以此达到优化性能的目的。

那么，我们重新回到代码，解读一下代码：
1、当我们第一次插入元素1时，列表已满（空列表没有空间存放数据），元素1本身要占8字节（指针），但是基于过度分配机制，列表会在分配给元素1空间后，额外分配24字节作为过度分配的空间，所以插入元素1后列表大小变成72， 72 = 40 + 8 + 24
2、当我们插入元素2时，发现列表空间还没满（之前过度分配了24字节），所以这次可以直接插入元素2，不必过度分配，因此列表大小还是72字节。

到这里，我们还可以知道，列表为了判断过度分配的时机，需要保存两个不同的变量，一个是之前提到的allocated，记录的是列表已分配的空间，在这个例子中，allocated就是4 = （72 - 40）// 8；另一个变量是列表实际保存元素的个数ob_size，这里是2。

如果我们一直执行插入元素的操作，那么列表用于保存数据的空间大小会这样变化：

temp = 0
l = list()
print(temp)
while (l.__sizeof__() - 40) // 8 <= 100:
    l.append(1)
    if (l.__sizeof__() - 40) // 8 != temp:
        print((l.__sizeof__() - 40) // 8)
    temp = (l.__sizeof__() - 40) // 8
# 0
# 4
# 8
# 16
# 25
# 35
# 46
# 58
# 72
# 88
# 106

这里输出数字的单位是“内存槽”，我们用内存槽的数量来衡量分配空间的大小，一个元素的指针占一个内存槽，内存槽可以直观地体现出此时列表允许保存的最大元素数。

显然，当列表为空时，内存槽数为0，之后第一次扩容，一口气扩容了4个内存槽。

我一开始学习的时候，以为扩容就是无脑一直4个4个扩容，但是当我观察输出结果后发现，好像扩容的规律没那么简单，所以上网找了不少资料，也走了不少挖路。

这里是列表扩容机制的公式，这个公式是对的，但是问题在于网上我看到的教程对于公式中变量的意义描述地不够清楚，甚至有些都描述错了。这里我用自己的理解来解释这个公式。

首先明确一个大前提，newsize是指插入新元素后，新老元素的内存槽数之和。
这点很重要，比如插入前列表中有10个元素，现在插入7个新元素，那么此时我们计算扩容的newsize就是10 + 7 = 17，而大部分文章都把newsize解释成新元素数量，这样的描述非常容易误导别人。

其次再明确一个大方向，就是每次扩容的内存槽数，只与newsize有关，即只与插入新元素后列表总元素数有关。

还要知道，并不是每次插入元素都需要扩容，是否需要扩容是根据newsize和allocated的大小来判断的。
当 allocated // 2 <= newsize <= allocated时，列表仅仅插入新元素，不进行扩容；只要newsize不在这个范围内时，才需要执行扩容。

具体计算公式是（这里用Pythonic写法改写了一下，意思都一样）：
new_allocated = newsize // 8 + 3 if newsize < 9 else 6
从这个式子中就可以清晰地看出，扩容空间雀食只和newsize有关。

根据这个思路，我在草稿纸上手工演算了一下扩容空间的变化：

# newsize      allocated // 2 <= newsize <= allocated    new_allocated      allocated
#   1                        False                         0 + 3 = 3        1 + 3 = 4  
#   2                        True                          None             4
#   3                        True                          None             4  
#   4                        True                          None             4
#   5                        False                         0 + 3 = 3        5 + 3 = 8
#   6 - 8                    True                          None             8
#   9                        False                         1 + 6 = 7        9 + 7 = 16
#   10- 16                   True                          None             16
#   17                       False                         2 + 6 = 8        17 + 8 = 25
#   18 - 25                  True                          None             25
#   26                       False                         3 + 6 = 9        26 + 9 = 35
#   27 - 25                  True                          None             35
#   36                       False                         4 + 6 = 10       36 + 10 = 46
#   37 - 46                  True                          None             46
#   47                       False                         5 + 6 = 11       47 + 11 = 58
#   48 - 58                  True                          None             58
#   59                       False                         7 + 6 = 13       59 + 13 = 72
#   60 - 72                  True                          None             72
#   73                       False                         9 + 6 = 15       73 + 15 = 88
#   74 - 88                  True                          None             88
#   89                       False                         11 + 6 = 17      89 + 17 = 106

观察最后列的allocated，发现和代码输出的一样，证明我们理解的正确。

最后值得一提的是，除了扩容，当列表删除元素时，也有可能发生缩容，也就是释放掉一些内存，计算缩容空间的公式和扩容完全一样，而判断是否需要缩容的条件也和扩容一样，具体就是当 newsize < allocated // 2时需要缩容。

到这里，Python列表的扩容机制也搞清楚了。

四、列表和元组初始化时的共有部分都有哪些内容

回顾第一点，我们讲了空列表和空元组相差的16字节都差了些什么，没有将列表除了这16字节外的24字节是什么。

这里的24字节，我查阅了一些资料，包含了下面这些状态信息：
1、列表用来存放数据的空间大小 allocated
2、列表对象的引用计数 ob_refcnt
3、两个结构体对象

其中红框内的变量是列表也有的，也就是那多出来的“16字节”的内容，其他变量就是构成剩余24字节的内容。而元组也有除红框外类似的内容，但却没有红框内的内容，所以空元组的大小是24字节。

另外，对于ob_size 和 allocated这两个变量的区别，我是用这个关系式来帮助理解的。（allocated表示列表已分配的空间，ob_size表示列表已经用来存放数据的空间）
allocated >= ob_size = len(list) >= 0

五、列表和元组的性能差异

这里老师给出了一个问题

# 创建空列表
# option A
empty_list = list()

# option B
empty_list = []

A 和 B两种方法，哪种方法创建空列表的效率更高呢？

首先从理论层面推测一下，方法A本质上是一个函数调用，Python解释器遇到函数调用会隐式调用函数栈，包括入栈出栈和参数检查的操作。而方法B是一个内置C函数，可以直接调用，绕过函数栈的操作以及参数检查。所以应该是方法B更快！

为了验证该想法，通过命令行测试一下即可：

python -m timeit "empty_list = list()"
5000000 loops, best of 5: 86 nsec per loop

python -m timeit "empty_list = []"
10000000 loops, best of 5: 30.4 nsec per loop

两者的差距还是比较大的。

另外再比较一下，创建空列表和空元组的性能差异

python -m timeit "empty_list = []"
10000000 loops, best of 5: 30.4 nsec per loop

python -m timeit "empty_tuple = ()"
10000000 loops, best of 5: 18.7 nsec per loop

这里就可以得出结论，直接通过内置C函数创建列表比通过函数调用创建列表要快，而同样通过内置C函数创建列表和元组，则是创建元组更快。