在计算机科学中，C3算法主要用在多重继承中，确定子类应该继承哪一个基类的方法。换句话说，C3超类线性化的输出是确定性的方法决定次序（MRO：Method Resolution Order）。
描述
C3算法得名于它的实现符合三个重要性质：基于一致性扩展（EPG）、保留局部优先次序和适合单调性准则，首次提出了C3超类线性化。它在2012年1月被适配到了Open Dylan实现，并跟从了一个增进的提议。将它选作方法解析的默认算法的语言有：Python 2.3、Raku、Parrot、Solidity和的面向对象语言模块。Perl 5语言从版本5.10.0起将它作为可选的、非默认的MRO。
Python创始人吉多·范罗苏姆这样总结C3超类线性化：“基本上，在C3背后的想法是，如果你写下在复杂的类层级中继承关系所施加的所有次序规则，这个算法将确定出满足所有这些规则的这些类的一个单调次序。如果不能确定出这样的次序，这个算法以失败告终。”
算法
一个类的C3超类线性化列表，是这个类的单例列表，串接上从并发的诸基类的线性化列表以及诸基类自身列表归并而成的唯一性序列化列表。这个算法要确定的单调次序类似于拓扑次序，诸基类自身列表作为给这个归并过程的最后实际参数，保持了这些直接基类的局部优先次序。
完成诸基类的线性化列表和诸基类列表的归并，就是选择这些列表的头部中第一个符合条件者，它可以同时出现为多个列表的第一个元素，但是禁止它出现在任何其他非头部位置。将选择的元素从以它作为头部的所有列表中移除，并将它填加到输出列表。重复选择并移除符合条件头部并扩展输出列表的过程，直到竭尽所有余下的列表。在这个处理过程中，如果由于所有余下列表的头部都出现在其他某个列表的非头部中，而没有选出符合条件的头部，则归并过程失败；在继承层级中的这种不一致性的依赖次序，导致这个类的线性化不存在。
计算一个类的线性化可以采用下文例子中演示的算法，在继承层级中找到这个类的所有基类，从根基类开始逐步进行归并处理。计算一个类的线性化还可以采用朴素分治算法，为求解这个类而递归的为归并子例程找到基类的线性化，但是它在用于存在环的类层级之时会导致无限循环递归，故而递归调用应当结合缓存或记忆化的优化方式。
例子
给定一个类Z的如下类层级：
类Z的线性化计算过程：
L(O) := [O] // O没有基类
L(A) := [A] + merge(L(O), [O])
= [A] + merge([O], [O])
= [A, O] // A只有单一基类
L(B) := [B, O]
L(C) := [C, O]
L(D) := [D, O]
L(E) := [E, O]
L(K1) := [K1] + merge(L(A), L(B), L(C), [A, B, C])
= [K1] + merge([A, O], [B, O], [C, O], [A, B, C]) // 选择A
= [K1, A] + merge([O], [B, O], [C, O], [B, C]) // 不选O，选择B
= [K1, A, B] + merge([O], [O], [C, O], [C]) // 不选O，选择C
= [K1, A, B, C] + merge([O], [O], [O]) // 选择O
= [K1, A, B, C, O]
L(K2) := [K2] + merge(L(D), L(B), L(E), [D, B, E])
= [K2] + merge([D, O], [B, O], [E, O], [D, B, E]) // 选择D
= [K2, D] + merge([O], [B, O], [E, O], [B, E]) // 不选O，选择B
= [K2, D, B] + merge([O], [O], [E, O], [E]) // 不选O，选择E
= [K2, D, B, E] + merge([O], [O], [O]) // 选择O
= [K2, D, B, E, O]
L(K3) := [K3] + merge(L(D), L(A), [D, A])
= [K3] + merge([D, O], [A, O], [D, A]) // 选择D
= [K3, D] + merge([O], [A, O], [A]) // 不选O，选择A
= [K3, D, A] + merge([O], [O]) // 选择O
= [K3, D, A, O]
L(Z) := [Z] + merge(L(K1), L(K2), L(K3), [K1, K2, K3])
= [Z] + merge([K1, A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K1, K2, K3]) // 选择K1
= [Z, K1] + merge([A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K2, K3]) // 不选A，选择K2
= [Z, K1, K2] + merge([A, B, C, O], [D, B, E, O], [K3, D, A, O], [K3]) // 不选A，不选D，选择K3
= [Z, K1, K2, K3] + merge([A, B, C, O], [D, B, E, O], [D, A, O]) // 不选A，选择D
= [Z, K1, K2, K3, D] + merge([A, B, C, O], [B, E, O], [A, O]) // 选择A
= [Z, K1, K2, K3, D, A] + merge([B, C, O], [B, E, O], [O]) // 选择B
= [Z, K1, K2, K3, D, A, B] + merge([C, O], [E, O], [O]) // 选择C
= [Z, K1, K2, K3, D, A, B, C] + merge([O], [E, O], [O]) // 不选O，选择E
= [Z, K1, K2, K3, D, A, B, C, E] + merge([O], [O], [O]) // 选择O
= [Z, K1, K2, K3, D, A, B, C, E, O] // 完成
Python
首先，定义一个元类来允许对象通过名字简明表示：
class Type(type):
def __repr__(cls):
return cls.__name__
class O(object, metaclass=Type): pass
根基类O通过名字O表示自身，而不采用默认表示形式。
下面定义一些基类，并接着构造这个继承树：
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
查看结果：
>> Z.__mro__
[Z, K1, K2, K3, D, A, B, C, E, O, ]
Raku
Raku默认的对类使用C3线性化：
class A {}
class B {}
class C {}
class D {}
class E {}
class K1 is A is B is C {}
class K2 is D is B is E {}
class K3 is D is A {}
class Z is K1 is K2 is K3 {}
say Z.^mro; # OUTPUT: ((Z) (K1) (K2) (K3) (D) (A) (B) (C) (E) (Any) (Mu))
Any和Mu是所有Raku对象从其继承的类型。
参考文献
评论 (0)