Python多继承C3算法分析

Python多继承MRO

在Python2.1中，采用了经典类，使用深度优先算法解析。

在Python 2.2中引入了一个新类，使用深度优先算法和广度优先算法。

Python 2.3以后的版本，经典类和新类并存，使用DFS算法和C3算法。

Python2中的经典类

class A(object):
    pass

Python3的新式类

class A:
    pass

C3算法

In computing, the C3 superclass linearization is an algorithm used primarily to obtain the order in which methods should be inherited (the "linearization") in the presence of multiple inheritance, and is often termed Method Resolution Order (MRO).

这是维基百科中的定义。下图是多重继承的关系图：

那么这里mro解析的顺序是怎样的呢？光看图片是很难分辨的。

C3线性算法的推导过程如下：

假设类C继承自父类B1，...Bn,类C的解析列表公式如下：

这个公式表明，C的解析列表是将其所有父节点及其父节点的解析列表合并在一起得到的。

merge操作分为如下几个步骤：

1.选取merge中的第一个列表记为当前列表K。

2.令h = head(K)，如果h没有出现在任何其他列表的尾部（除了列表中的第一个元素，其余称为尾部），然后将其添加到类C的线性化列表中，并将其从合并中的所有列表中删除，然后重复步骤 2。

3.否则，设置K为merge的下一个列表，重复2中的操作。

4.如果merge的类全部去掉，则输出类创建成功；如果找不到下一个 h，则输出类 C 抛出异常。

推导过程

我们用上图来推导一下mro的解析顺序。

上面那张图转换为python代码如下：

转换成Python代码

O = object
class A(O): pass
class B(O): pass
class C(O): pass
class D(O): pass
class E(O): pass
class K1(A, B, C): pass
class K2(D, B, E): pass
class K3(D, A): pass
class Z(K1, K2, K3): pass
print(Z.mro())

推导

L(K1) = K1 + merge(L[A],L[B],L[C],(A,B,C))
      = K1 + merge(L[A,O],L[B,O],L[C,O],(A,B,C))
      = [K1,A] + merge(L[O],L[B,O],L[C,O],(B,C))
      = [K1,A,B] + merge(L[O],L[O],L[C,O],(C))
      = [K1,A,B,C] + merge(L[O],L[O],L[O])
      = [K1,A,B,C,O]
L(K2) = [K2,D,B,E,O]
L(K3) = [K3,D,A,O]
以上是K1,K2,K3的解析顺序
下面是Z的推导过程
L(Z) = Z + merge(L(K1)+L(K2)+L[K3],(K1,K2,K3))
     = Z + merge(L[K1,A,B,C,O]+L(K2,D,B,E,O)+L(K3,D,A,O),(K1,K2,K3))
     = [Z,K1] + merge(L[A,B,C,O]+L(K2,D,B,E,O)+L(K3,D,A,O),(K2,K3))
     = [Z,K1,K2] + merge(L[A,B,C,O]+L(D,B,E,O)+L(K3,D,A,O),(K3))
     = [Z,K1,K2,K3] + merge(L[A,B,C,O]+L(D,B,E,O)+L(D,A,O))
     = [Z,K1,K2,K3,D] + merge(L[A,B,C,O]+L(B,E,O)+L(A,O))
     = [Z,K1,K2,K3,D,A] + merge(L[B,C,O]+L(B,E,O)+L(O))
     = [Z,K1,K2,K3,D,A,B] + merge(L[C,O]+L(E,O)+L(O))
     = [Z,K1,K2,K3,D,A,B,C] + merge(L[O]+L(E,O)+L(O))
     = [Z,K1,K2,K3,D,A,B,C,E,O]

我们得出的最终答案为：Z的解析顺序：Z->K1->K2->K3->D->A->B->C->E->O

为了验证答案，我们在python中运行

print(Z.mro())

结果如下

[<class '__main__.Z'>, <class '__main__.K1'>, <class '__main__.K2'>, <class '__main__.K3'>, <class '__main__.D'>,
<class '__main__.A'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.E'>, <class 'object'>]

和我们推导的结果相同，这就是C3算法的流程。