学者须先立志。今日所以悠悠者，只是把学问不曾做一件事看，遇事则且胡乱恁地打过了，此只是志不立。——朱熹
1. 前言
在计算机科学中，C3算法主要用于确定多重继承时，子类应该继承哪一个父类的方法，即方法解析顺序(Method Resolution Order，MRO)。
2. C3算法实现了三种重要特性
- 保持继承拓扑图的一致性。
- 保证局部优先原则（又称：本地优先级，比如A继承C，C继承B，那么A读取父类方法，应该优先使用C的方法而不是B的方法）。
- 保证单调性原则（即子类不改变父类的方法搜索顺序，如：如果在C的解析顺序中，A排在B的前面，那么在C的所有子类里，也必须满足这个顺序）。
3. 为什么采用C3算法
C3主要用于在多继承时判断继承调用的路径(来自于哪个类)。
在Python2.3之前是基于深度优先算法，为了解决原来基于深度优先搜索算法不满足本地优先级，和单调性以及继承不清晰的问题，从Python2.3起应用了新的C3算法。在Python官网的The Python 2.3 Method Resolution Order中作者举了例子，说明这一情况。
F=type('Food', (), {remember2buy:'spam'}) E=type('Eggs', (F,), {remember2buy:'eggs'}) G=type('GoodFood', (F,E), {})
根据本地优先级在调用G类对象属性时应该优先查找F类。
但是在Python2.3之前的算法给出的顺序是GEFO， 而在C3算法中通过阻止类层次不清晰的声明来解决这一问题，以上声明在C3算法中就是非法的。
4. C3算法精讲
判断mro要先确定一个线性序列，然后查找路径由序列中类的顺序决定。所以C3算法就是生成一个线性序列。
如果继承至一个基类： class B(A) 这时B的mro序列为[B,A] 如果继承至多个基类： class B(A1,A2,...,An) 这时B的mro序列： mro(B) = [B] + merge(mro(A1), mro(A2),...,mro(An), [A1,A2,...,An]) merge操作就是C3算法的核心，是递归运算。
遍历执行merge操作的序列，如果一个序列的第一个元素，在其他序列中也是第一个元素，或不在其他序列出现， 则从所有执行merge操作序列中删除这个元素，合并到当前的mro中。merge操作后的序列，递归地执行merge操作，直到merge操作的序列为空。
如果merge操作的序列无法为空，则说明不合法。
例子1：
class A(object):pass class B(object):pass class C(object):pass class E(A,B):pass class F(B,C):pass class G(E,F):pass
A、B、C都继承至一个基类，所以mro序列依次为[A,O]、[B,O]、[C,O]
我们接下来看下E的mro如何求解：
mro(E) = [E] + merge(mro(A), mro(B), [A,B]) = [E] + merge([A,O], [B,O], [A,B])
执行merge操作的序列为[A,O]、[B,O]、[A,B] A是序列[A,O]中的第一个元素，在序列[B,O]中不出现，在序列[A,B]中也是第一个元素， 所以从执行merge操作的序列([A,O]、[B,O]、[A,B])中删除A，合并到当前mro[E]中。
mro(E) = [E,A] + merge([O], [B,O], [B])
再执行merge操作，O是序列[O]中的第一个元素，但O在序列[B,O]中出现并且不是其中第一个元素。继续查看[B,O]的第一个元素B，B满足条件， 所以从执行merge操作的序列中删除B，合并到[E, A]中。
mro(E) = [E,A,B] + merge([O], [O]) = [E,A,B,O]
同理
mro(F) = [F] + merge(mro(B), mro(C), [B,C]) = [F] + merge([B,O], [C,O], [B,C]) = [F,B] + merge([O], [C,O], [C]) = [F,B,C] + merge([O], [O]) = [F,B,C,O] mro(G) = [G] + merge(mro[E], mro[F], [E,F]) = [G] + merge([E,A,B,O], [F,B,C,O], [E,F]) = [G,E] + merge([A,B,O], [F,B,C,O], [F]) = [G,E,A] + merge([B,O], [F,B,C,O], [F]) = [G,E,A,F] + merge([B,O], [B,C,O]) = [G,E,A,F,B] + merge([O], [C,O]) = [G,E,A,F,B,C] + merge([O], [O]) = [G,E,A,F,B,C,O]
例子2
再看一个复杂的例子： class A(object):pass class B(object):pass class C(object):pass class D(object):pass class E(object):pass class FA(A, B, C):pass class FB(D, B, E):pass class FC(D, A):pass class SF(FA, FB, FC): pass
你可以尝试着自己计算一下MRO List，当然，最后你需要用python自带的.mro()进行验证。
5.关注公众号
微信公众号：堆栈future
