[数据结构与算法]Python 底层原理

1. 心得体会

? ? ? ? 最近在学习一些 Python 底层原理的干货知识，从 python 底层的 C 代码真的是了解到了很多东西。让我明白了 Python 是如何处理各种变量类型的，也明白了 Python 是如何管理变量的。在这个过程中我也在学习过程中想通了以前遇到的一些当时认为很奇葩的现象，如 del 掉一个变量后新建一个变量偶尔会发现新建的变量和 del 的变量的地址是一样的，这本质上还是对 Python 原理不清楚所导致的。

? ? ? ? 另外，我在学习中也参考了大佬的文章，感兴趣的可以看看他的文章，写得非常详细：https://pythonav.com/wiki/detail/6/88/

2. 变量原理

? ? ? ? 很多人都知道 Python 底层是 C 语言实现的，那如 float、str、int、tuple、dict 等变量类型在它底层是如何处理的呢？事实上，这些变量类型都是 C 语言中的结构体。而 float、tuple 等变量类型实现的功能虽然不一样，但所有变量类型底层都有共同的结构体，或者说“基结构体”。结构中都有四个变量，上一个对象指针、下一个对象指针、引用计数器、数据类型。在这个“基结构体”的基础上来实现的 Python 的变量类型。

2.1 双向循环链表

? ? ? ? “上一个对象指针、下一个对象指针是用来干什么的呢？”

? ? ? ? 这是 Python 为了方便管理所有的变量而将所有创建的变量都通过双向循环链表来管理，所有的变量都要放进这个链表中。所以才有上一个对象指针、下一个对象指针作为。

? ? ? ? “引用计数器作用是什么？”

? ? ? ? 这是 Python 为了方便管理变量而设计的。对每个新建的变量，引用计数器初始化为1，到0的时候就意味着这个变量没有用了，通过遍历双向循环链表找到这个变量，再删除这个变量。

2.2 循环引用问题

? ? ? ? “什么是循环引用问题？”

? ? ? ? 上面提到了引用计数器的作用，那你可能会想到像列表元组这种特殊的变量，它可以彼此引用，那这时候如果没有对应的机制来解决这个问题的话，循环引用可能会导致变量无法删除，长期以往系统内存就会莫名其妙的撑爆。

>>> a = [1,2,3,4]
>>> b = [4,3,2,1]
>>> a.append(b)
>>> a
[1, 2, 3, 4, [4, 3, 2, 1]]
>>> b.append(a)
>>> b
[4, 3, 2, 1, [1, 2, 3, 4, [...]]]

? ? ? ? “Python 是如何解决循环引用问题的呢？”

? ? ? ? 采用标记消除的方法。这个标记是指“引用计数器”，之前也提到引用计数器的作用。Python 会在底层再维护一个链表，专门放那些可能造成循环引用的对象（list、tuple、dict、set）。在某种条件下，扫描这个链表中的每一个元素，检查是否有循环引用，如有，则让双方的引用计数器-1，如果减到0，则回收。

? ? ? ? “什么时候扫描这个链表呢？”

? ? ? ? 因为扫描循环引用链表代价较大，耗时久，所以 Python 采用分代回收机制。它l将可能存在循环引用的对象维护成3个双向循环链表。这儿我们分别称呼它为0代、1代、2代。

• 0代：0代对象个数达到700个扫描1次。
• 1代：0代扫描10次时，1代扫描1次。
• 2代：1代扫描10次时，2代扫描1次。

? ? ? ? 第1次扫描0代，不是垃圾的变量就放到1代。当扫描1代时，不是垃圾变量就放到2代中。这个机制看似相当 nice，但是你仔细思考，它还有相当的改动空间。

2.3 缓存机制

? ? ? ? “Python 在分代回收之上还有什么优化机制呢？”

? ? ? ? Python 缓存机制。Python 为了避免重复创造和销毁一些常见对象，来维护了一个缓存池。下面为了生动形象解释 Python 是否有这个机制，我们可以随意创建和删除变量，再去查看它们的地址，如果地址一样说明 Python 是缓存了删除的变量地址。

>>> a = 1
>>> b = [1,2,3]
>>> c = {'a': '1'}
>>> id(a)
140719620653328
>>> id(b)
1634667746312
>>> id(c)
1634667730968
>>> del a
>>> a = 3
>>> id(a)
140719620653392
>>> d = 1
>>> id(d)
140719620653328
>>> del b
>>> f = [1,2,3]
>>> id(f)
1634667746312

? ? ? ? 从代码中我们可以看到，明明 del 了的变量，再生成与之相同值的变量的时候，地址是一样的。但是你可能会想：

? ? ? ? “是不是 Python 把值一样的变量都指向了同一个地址呢？”（然后抛出以下代码）

>>> aa = 1
>>> id(aa)
140719620653328

????????“aa 地址和 a是一样的哎！”

? ? ? ? 这是明显不可能的，甚至是很笨的想法（如果是这样的话，我修改一个地址的内容的话，所有指向这个地址的变量的值都会改变，这样 Python 就会乱套了），但是这是一个有趣的现象，这引出了 Python 缓存机制的另一点：启动 Python 解释器的时候，Python 会先创建 -5 ~ 257 这个范围内整数的地址（Python3 版本）,且这个范围内的变量引用计数器不会被减为0。

? ? ? ? “这个缓存池会如何运转呢？会一直缓存删除的变量的地址吗？”

? ? ? ? 它不会无限制地缓存，Python 底层中是由名为 free_list 的列表来存放的，且 Python3 中每种数据类型都有一个缓存个数的上限。据代码中所设计的，int 型可缓存100个；list 型可缓存80个，dict 型可缓存80个；tuple 型可缓存20个，且是元素个数从0到19的链表（即每个链表最多2000个元素）。

? ? ? ? “只有 int 型在解释器运行时会创建固定值的地址吗？其它类型呢？”

? ? ? ? 不止 int 型，例如 str，针对只含有字母、数字、下划线等特殊字符，创建同样内容字符串的地址相同。这种机制被称为驻留机制。

>>> str1 = "1"
>>> id(str1)
1634668919280
>>> str2 = "1"
>>> id(str2)
1634668919280

2.4 关于 dict?

? ? ? ? “很多书本上都说字典元素(dict)是无序的，但是我在最近的面试题中却说是有序的，这是为什么？”（字节面试题）

? ? ? ? 这个其实是一个很微妙（有点哭笑不得）的事情。首先要知道一点，Python 底层实现不是不变的，书上说的无序是在 Python3.5，在 Python3.6 开始，字典不再是无序的了，而是遵从 hash 算法的排序！很多书出版较早，所以说法上有些不同，所以一定要注意版本问题。每个版本发布，都会对之前的版本做一些改动，对于比较关键的改动一定要注意！

? ? ? ? “既然说 dict 是有序的，大概是如何排序的呢？”

? ? ? ? 在 Python3.6?中，字典索引 key 通过 hash 算法计算出一个值，这个值来作为 value 的索引。但是你想，hash 算法的结果是固定位数的值，而作为 key 的值可以说是无限种可能的，就很有可能出现不同的 key ，hash 出一样的值出来，这被称为哈希冲突。为了避免哈希冲突，现在有好几种方案，如有线性探测法、二次探测法、线性探测。Python 采用二次探测法来解决哈希冲突。即遇到冲突时，索引再加或减遇到冲突次数的平方。

2.5 关于 list

? ? ? ? “一直很好奇，Python 的 list 是如何做到像 C 那样很难做到的动态扩容的？Python list 的操作真的太方便啦！”

? ? ? ? 首先，我们之前也提到过的，无论什么数据类型的变量，都会有引用计数器、数据类型、上一个对象指针、下一个对象指针，而 list 除了这四个之外，还有一个元素记录元素个数以及一个数组来存放指针的指针的值（C语言中的双指针），这就是为什么 list 会有深复制和浅复制的区别。关于扩容和缩容，底层通过 realloc 开辟内存，基于一个公式进行扩容缩容：

? ? ? ? (x + (x >> 3) + 6) & - 3

? ? ? ? 每次容量改变都会重新设置列表内容。值得一提的是，pop 函数只是把已占容量-1，不真正删除地址值。

底层还有很多内容没有提到，仅以此文记录2021-8月的学习。希望日后还有机会补完吧。

Talk is cheap, show me the?code ——?薪火工作室箴言

散是满天星，聚是兴薪之火。