C3线性化

C3算法最早被提出是用于Lisp的，应用在Python中是为了解决原来基于深度优先搜索算法不满足本地优先级，和单调性的问题。 本地优先级：指声明时父类的顺序，比如C(A,B)，如果访问C类对象属性时，应该根据声明顺序，优先查找A类，然后再查找B类。 单调性：如果在C的解析顺序中，A排在B的前面，那么在C的所有子类里，也必须满足这个顺序。C3算法将多重继承的树状结构继承关系实现线性化，生成一个线性序列，确定了子类查找父类方法的优先顺序。

MRO

MRO 全称方法解析顺序（Method Resolution Order），它决定基类中的函数到底应该以什么样的顺序调用父类中的函数。

大体顺序如下：

for(遍历执行merge操作的序列){
    if(一个序列的第一个元素在其他序列中也是第一个元素 || 不在其他序列出现){
        从所有执行merge操作序列中删除这个元素
        合并到当前的mro中
    }

    if(merge操作的序列为空){
        done;
    }

    if(最后一次merge操作完成 && merge操作的序列无法为空){
        throw;
        该继承不合法
    }

}

示例：

class A(O)
class B(O)
class C(O)
class E(A,B)
class F(B,C)
class G(E,F)

意思是：A 继承O，B继承O，C继承O；E继承A和B，F继承B和C，G继承E和F。

分析E：

[E] = [E] + merge([A], [B], [A,B])
= [E] + merge([A,O], [B,O], [A,B])

因为 A是序列[A,O]中的第一个元素，而且在序列[B,O]中不出现，而且在序列[A,B]中也是第一个元素，所以删除A、合并到E，得：

[E] = [E,A] + merge([O], [B,O], [B])

继续分析：

• O是序列[O]中的第一个元素，但O在序列[B,O]中出现并且不是其中第一个元素，因此不能合并

• B是[B,O]的第一个元素，所以删除B，合并到E，得：

• [E] = [E,A,B] + merge([O], [O])
  

两个[O] 可以直接合并了，因此最终结果是 ： [E,A,B,O]

推导F也是一样的道理，在这里建议读者不妨先自己推理一遍，然后再对照答案。

(F) = [F] + merge([B], [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]