01-Python 高级特性

Python 垃圾回收机制 ★★★★★

参考：Python内存管理以及垃圾回收机制

点评：当面试官问到这个问题的时候，一个展示自己的机会就摆在面前了。你要先反问面试官：“你说的是官方的 CPython 解释器吗？”。这个反问可以展示出你了解过 Python 解释器的不同的实现版本，而且你也知道面试官想问的是 CPython。当然，很多面试官对不同的 Python 解释器底层实现到底有什么差别也没有概念。所以，千万不要觉得面试官一定比你强，怀揣着这份自信可以让你更好的完成面试。

Python 提供了自动化的内存管理，也就是说内存空间的分配与释放都是由 Python 解释器在运行时自动进行的，自动管理内存功能极大的减轻程序员的工作负担，也能够帮助程序员在一定程度上解决内存泄露的问题。以 CPython 解释器为例，它的内存管理有三个关键点：引用计数、标记-清理、分代收集。

简单来说：Python 垃圾回收机制，主要使用 引用计数 来跟踪和回收垃圾。在 引用计数 的基础上，通过 标记-清除 解决容器对象可能产生的循环引用问题。通过 分代回收 以空间换时间的方法提高垃圾回收效率。

  • 引用计数。
    在 Python 的 C 源码中有一个名为 refchain 的环状双向链表，Python 程序中一旦创建对象都会把这个对象添加到 refchain 这个链表中。
    在 refchain 中的所有对象内部都有一个 ob_refcnt 用来保存当前对象的引用计数器，顾名思义就是自己被引用的次数。
    当一个对象有新的引用时，它的 ob_refcnt 就会增加，当引用它的对象被删除，它的 ob_refcnt 就会减少。引用计数为 0 时，该对象生命就结束了。
    优点:1.简单。2.实时性。
    缺点:1.维护引用计数消耗资源。2.存在循环引用的话，不能删除。

    以下情况会导致引用计数加1：

    • 对象被创建
    • 对象被引用
    • 对象作为参数传入到一个函数中
    • 对象作为元素存储到一个容器中

    以下情况会导致引用计数减1：

    • 用 del 语句显示删除对象引用
    • 对象引用被重新赋值其他对象
    • 一个对象离开它所在的作用域
    • 持有该对象的容器自身被销毁
    • 持有该对象的容器删除该对象

    可以通过 sys 模块的 getrefcount 函数来获得对象的引用计数。引用计数的内存管理方式在遇到循环引用的时候就会出现致命伤，因此需要其他的垃圾回收算法对其进行补充。

  • 标记-清除。
    基于引用计数器进行垃圾回收非常方便和简单，但他还是存在循环引用的问题，导致无法正常回收一些数据。
    基本思路是先按需分配，等到内存中的对象打到一定阈值之后，会触发标记清除机制。
    创建特殊链表专门用于保存列表、元组、字典、集合、自定义类等对象，之后再去检查这个链表中的对象是否存在循环引用，如果存在则让双方的引用计数器均 -1。

    该算法在垃圾回收时分为两个阶段：

    • 标记阶段，遍历所有的对象，如果对象是可达的（被其他对象引用），那么就标记该对象为可达；
    • 清除阶段，再次遍历对象，如果发现某个对象没有标记为可达，则就将其回收。

    CPython 底层维护了两个双端链表，一个链表存放着需要被扫描的容器对象（姑且称之为链表A），另一个链表存放着临时不可达对象（姑且称之为链表B）。

    为了实现“标记-清除”算法，链表中的每个节点除了有记录当前引用计数的 ref_count 变量外，还有一个 gc_ref 变量，这个 gc_ref 是 ref_count 的一个副本，所以初始值为 ref_count 的大小。

    执行垃圾回收时，首先遍历链表A中的节点，并且将当前对象所引用的所有对象的 gc_ref 减 1，这一步主要作用是解除循环引用对引用计数的影响。
    再次遍历链表A中的节点，如果节点的 gc_ref 值为0，那么这个对象就被标记为“暂时不可达”（GC_TENTATIVELY_UNREACHABLE）并被移动到链表B中；如果节点的gc_ref不为0，那么这个对象就会被标记为“可达“（GC_REACHABLE），对于”可达“对象，还要递归的将该节点可以到达的节点标记为”可达“；链表B中被标记为”可达“的节点要重新放回到链表A中。
    在两次遍历之后，链表B中的节点就是需要释放内存的节点。

  • 分代回收。
    分代回收的整体思想是对标记清除中的链表进行优化，将那些可能存在循引用的对象拆分到3个链表，链表称为：0/1/2三代，每代都可以存储对象和阈值，当达到阈值时，就会对相应的链表中的每个对象做一次扫描。
    扫描会遍历链表中的每个对象，如果存在循环引用，就将存在循环引用的对象的引用计数器 -1，同时 Python 解释器也会将计数器等于0（可回收）和不等于0（不可回收）的一分为二，把计数器等于0的所有对象进行回收，把计数器不为0的对象放到另外一个双向链表表（即：分代回收的下一代）
    0代和1、2代的 threshold 和 count 表示的意义不同。

    • 0代，count 表示0代链表中对象的数量，threshold 表示0代链表对象个数阈值，超过则执行一次0代扫描检查。
    • 1代，count 表示0代链表扫描的次数， threshold 表示0代链表扫描的次数阈值，超过则执行一次1代扫描检查。
    • 2代，count 表示1代链表扫描的次数， threshold 表示1代链表扫描的次数阈值，超过则执行一2代扫描检查。
      分代回收扫描的门限值可以通过 gc 模块的 get_threshold 函数来获得，该函数返回一个三元组，分别表示多少次内存分配操作后会执行 0 代垃圾回收，多少次 0 代垃圾回收后会执行 1 代垃圾回收，多少次 1 代垃圾回收后会执行 2 代垃圾回收。需要说明的是，如果执行一次 2 代垃圾回收，那么比它年轻的代都要执行垃圾回收。如果想修改这几个门限值，可以通过 gc 模块的 set_threshold 函数来做到。

  • 缓存机制
    从上文大家可以了解到当对象的引用计数器为 0 时，就会被销毁并释放内存。
    而实际上他不是这么的简单粗暴，因为反复的创建和销毁会使程序的执行效率变低。Python中引入了 缓存机制 机制。
    例如：引用计数器为 0 时，不会真正销毁对象，而是将他放到一个名为 free_list 的链表中，之后会再创建对象时不会在重新开辟内存，而是在 free_list 中将之前的对象来并重置内部的值来使用。

GIL 全局解释器锁（global interpreter lock） ★★★★★

GIL 全局解释器锁，每个线程在执行时候都需要先获取 GIL，保证同一时刻只有一个线程可以执行代码，即同一时刻只有一个线程使用 CPU，以此来控制同一时间内共享数据只能被一个任务所修改，进而保证数据安全。也就是说多线程并不是真正意义上的同时执行。

对于 io 密集型任务，Python 的多线程起到作用，但对于 cpu 密集型任务，Python 的多线程几乎占不到任何优势，还有可能因为争夺资源而变慢。解决办法就是多进程和协程(协程也只是单CPU，但是能减小切换代价提升性能)。

GIL 保护的是解释器级的数据，保护用户自己的数据则需要自己加锁处理。

list 底层原理

List 和 tuple

List 本质是大小可以动态改变的顺序表或者数组(指针数组)，增删改查都是通过索引去修改对应位置的数据（通过角标配合表头物理地址，计算目标元素的位置），因为 list 里面存的数据可以是各种类型的，所以 List 实际存储的是对应对象的指针（或者叫内存地址）。

tuple 本质上和 List 一样，但是不可修改不可扩容，只读。

dict 底层原理 ★★★★★

list 索引取值是 o(1), 查找是 o(n)
dict 取值和查找都是 o(1)

Dict 和 Set

dict：本质上也是顺序表或者数组(指针数组)，3.6 之前和 3.6 之后实现细节不太一样。

  • 在3.6版本之前，Python Dict 底层在初始创建的时候采用的是 indice 和存储合并在一个二维数组当中。Dictionary 采用哈希表原理，key 作为取值对象，进行 hash(key) 操作，得到哈希值，然后用值进行 % 字典容量得到要插入的位置。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    my_dict = {}
    my_dict['age'] = 26
    my_dict['salary'] = 999999

    """
    # Dictionary结构
    [
        [-4234469173262486640, '指向salary的指针', '指向999999的指针'],
        [1545085610920597121, '执行age的指针', '指向26的指针'],
        [---, ---, ---],
        [---, ---, ---],
        [---, ---, ---],
        [1278649844881305901, '指向name的指针', '指向kingname的指针'],
        [---, ---, ---],
        [---, ---, ---]
    ]
    """

    取值和存放都是进行 hash 然后取模，直接访问这个二维数组。
    循环遍历字典的 Key 的时候，Python 底层会遍历这个二维数组，如果当前行有数据，那么就返回Key指针对应的内存里面的值。如果当前行没有数据，那么就跳过。所以总是会遍历整个二位数组的每一行。

  • 在版本3.6之后，字典的底层数据结构发生了变化，现在当你初始化一个空的字典以后，它在底层是这样的：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    my_dict = {}
    my_dict['address'] = 'xxx'
    my_dict['salary'] = 999999

    ## 此时的内存示意图
    indices = [1, 0, None, None, None, None, 2, None]

    entries = [
        [-5954193068542476671, '指向name的指针', '执行kingname的指针'],
        [9043074951938101872, '指向address的指针','指向xxx的指针'],
        [7324055671294268046, '指向salary的指针', '指向999999的指针']
    ]

    实际数据存储和索引进行分开存放，indices 是数据存放在二维数组的位置，其他内容保持不变。这样就保证了 Dictionary 在添加新的键值对的时候是按照顺序进行依次存放的。当去读取 dict 内容的时候

    1
    2
    hash('salary')      # 7324055671294268046
    hash('salary') % 8  # 6

    那么我就去读 indices 下标为 6 的这个值。这个值为 2，然后再去读 entries 里面，下标为 2 的这一行的数据，也就是 salary 对应的数据了。

set 实现去重本质上是通过 __hash__ 和 __eq__ 来实现对每个元素的 hash 散列，判断 hash 值是否一致；一致的话，判断对象是否具有一模一样的方法和属性，如果都一致，则去重；因此，set 元素也必须是可 hash 的；

set 本质也是 dict，只不过其键值都一样。

去重过程：首先对 key 进行 hash，在 dict 中这一步是为了获取 value 的索引，这里也一样；如果索引相同，说明要么数据重复了，要么 key 发生了 hash 碰撞，这时候就去比较两个 key 对应的 value 是否相同，如果也相同，确认是数据重复，则去重（保留最新的那个）；如果数据不同，说明只是在当前 hash 算法中，两个 key 刚好发生了hash碰撞（概率相当低），此时不会发生去重；

Hash 冲突

Python2 中使用 开放地址法 解决 Hash 冲突。

开放寻址法（open addressing）：所有的元素都存放在散列表里，当产生哈希冲突时，通过一个探测函数计算出下一个候选位置，如果下一个获选位置还是有冲突，那么不断通过探测函数往下找，直到找个一个空槽来存放待插入元素。

开放地址的意思是除了哈希函数得出的地址可用，当出现冲突的时候其他的地址也一样可用，常见的 开放地址思想 的方法有线性探测再散列，二次探测再散列等，这些方法都是在第一选择被占用的情况下的解决方法。

补充：

字典和集合的工作原理

不同于其他数据结构，字典和集合的内部结构都是一张哈希表。

  • 对于字典而言，这张表存储了哈希值（hash）、键和值这 3 个元素。
  • 对于集合来说，区别就是哈希表内没有键和值的配对，只有单一的元素了。

插入操作

每次向字典或集合插入一个元素时，Python 会首先计算键的哈希值（hash(key)），再和 mask=PyDicMinSize-1 做与操作，计算这个元素应该插入哈希表的位置 index=hash(key)&mask。

  • 如果哈希表中此位置是空的，那么这个元素就会被插入其中。
  • 如果此位置已被占用，Python 便会比较两个元素的哈希值和键是否相等。
    • 若两者都相等，则表明这个元素已经存在
    • 若两者中有一个不相等，这种情况我们通常称为哈希冲突（hash collision），意思是两个元素的键不相等，但是哈希值相等。这种情况下，Python 便会继续寻找表中空余的位置，直到找到位置为止。值得一提的是，通常来说，遇到这种情况，最简单的方式是线性寻找，即从这个位置开始，挨个往后寻找空位。

查找操作

和前面的插入操作类似，Python 会根据哈希值，找到其应该处于的位置；然后，比较哈希表这个位置中元素的哈希值和键，与需要查找的元素是否相等。如果相等，则直接返回；如果不等，则继续查找，直到找到空位或者抛出异常为止。

删除操作

对于删除操作，Python 会暂时对这个位置的元素，赋于一个特殊的值，等到重新调整哈希表的大小时，再将其删除。

哈希冲突

哈希冲突的发生，往往会降低字典和集合操作的速度。因此，为了保证其高效性，字典和集合内的哈希表，通常会保证其至少留有 1/3 的剩余空间。随着元素的不停插入，当剩余空间小于 1/3 时，Python 会重新获取更大的内存空间，扩充哈希表。不过，这种情况下，表内所有的元素位置都会被重新排放。虽然哈希冲突和哈希表大小的调整，都会导致速度减缓，但是这种情况发生的次数极少。所以，平均情况下，这仍能保证插入、查找和删除的时间复杂度为 O(1)。

#Python #面试
01-Python 高级特性
https://flepeng.github.io/interview-20-开发语言类-21-Python-01-Python-高级特性/
作者
Lepeng
发布于
2020年8月8日
许可协议