Python - Super()继承顺序 - MRO顺序C3算法解析

1. 拓扑排序算法

在解析MRO之前，需要先理解拓扑排序（Topological Sorting）算法

在图论中，当有向无环图（Directed Acyclic Graph,简称DAG）的所有顶点组成一个线性序列，且该序列满足以下条件：
1.每个顶点出现且只出现一次；
2.若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
则称该序列是此DAG的一个拓扑排序。

那么这个序列是如何得到的呢？

1.选择一个入度为0（即只有出边没有入边）的顶点并输出；
2.删除此顶点及所有出边。
循环执行上面两步直到不存在入度为0的顶点为止，顶点输出的顺序即为拓扑排序。

用图比较容易理解：

拓扑排序得到的序列为：5 → 4 → 2 → 3 → 1

注意：在某些情况下拓扑排序可有多个结果

2. MRO - C3算法的工作原理

Python的Super()函数的方法解析顺序（Method Resolution Order, 简称MRO）使用的C3算法，可以理解为在拓扑排序算法的基础上考虑了基类出现的先后顺序。

C3算法的本质就是Merge，Merge规则如下：
取第一序列的第一元素，与所有后续序列除第一元素外的所有元素进行比较。
若不存在相同者，则取出这个元素并从全部序列中删除；
若存在，则跳过此序列，取下一序列的第一元素往后进行相同的比较，直到可以取出某个元素并从全部序列中删除。
然后回到最前面的序列，取第一元素进行下一轮循环比较，直到取出所有元素。取出的元素组成的列表即为__mro__列表。

之所以使用这个算法，是因为基于深度优先的搜索算法（见后文）不满足本地优先级和单调性的需求。
本地优先级：指声明时父类的顺序，比如D(B,C)，则访问D类对象属性时，应该优先查找B，然后再查找C。
单调性：如果在D的解析顺序中，B在C的前面，那么在D的所有子类里，也必须满足这个顺序。

试看以下代码

class A(object):
    pass

class B(A):
    pass

class C(A):
    pass

class D(B, C):
    pass

class E(D, C):
    pass

假设X.mro = L(X), +为merge，则C3算法的过程为：

L(E) = E + L(D) + L(C) + DC
L(E) = E + [D+L(B)+L(C)+BC] + [C+L(A)+A] + DC
L(E) = E + [D + [B+L(A)+A] + [C+L(A)+A] + BC] + [C+A+A] + DC
L(E) = E + [D + BA + CA + BC] + CA + DC
L(E) = E + DBCA + CA + DC
L(E) = EDBCA

排序结果为：E → D → B → C → A → object

到此为止，基本可以理解MRO的排序算法的运算过程了。

3. 如何直接查看某个类的继承顺序？

每个类都有对应的__mro__属性和mro()方法：

1 2	E.__mro__ E.mro()

1
2

(<class '__main__.E'>, <class '__main__.D'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.A'>, <class 'object'>)
[<class '__main__.E'>, <class '__main__.D'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.A'>, <class 'object'>]

4. 什么是深度优先算法？

这是Python2.3之前的版本所使用的搜索算法，也是所有Python2.x版本中默认的经典类的搜索算法。

试看以下代码在2.2版本中的搜索结果：

class A():
    def foo():
        print("in A")

class B(A):
    # def foo():
    #     print("in B")
    pass

class C(A):
    def foo():
        print("in C")

class D(B, C):
    pass

D().foo()

in A

按照深度优先的原则: D → B → A → C，当B或A中有foo()方法时，根本轮不到去找C类中的foo()方法！

为了解决这个问题，在Python2.3版本引入了新式类（使用C3算法），但是必须显式的声明继承自object才能生效。

1
2
3

class A(object):
    pass
···

Python3.x版本所有类默认为新式类，不必显式的声明。
另：经典类中所有的特性都是可读可写的, 新式类中的特性只读的, 只能通过添加特性达到目的。

5. 引申：广度优先算法

广度优先算法是优先查找距离最近的节点，即横向查找。
则上面的代码排序结果为：D → B → C → A
而使用第二部分的代码，排序结果为：E → D → C → B → A → object