Python多重繼承問題之MRO和C3算法

多繼承衷快、 MRO 及 C3算法關系

在計算機科學中拷肌，C3算法主要用于確定多重繼承時蜓谋，子類應該繼承哪一個父類的方法区匣，即方法解析順序（Method Resolution Order偷拔，MRO）蒋院。

C3算法實現(xiàn)了三種重要特性：

保持繼承拓撲圖的一致性亏钩。
保證局部優(yōu)先原則（比如A繼承C，C繼承B欺旧，那么A讀取父類方法姑丑，應該優(yōu)先使用C的方法而不是B的方法）。
保證單調(diào)性原則（即子類不改變父類的方法搜索順序）辞友。

為什么采用C3算法

C3主要用于在多繼承時判斷繼承調(diào)用的路徑(來自于哪個類)栅哀。在Python2.3之前是基于深度優(yōu)先算法，為了解決原來基于深度優(yōu)先搜索算法不滿足本地優(yōu)先級称龙，和單調(diào)性以及繼承不清晰的問題留拾，從Python2.3起應用了新的C3算法。在Python官網(wǎng)的The Python 2.3 Method Resolution Order中作者舉了例子鲫尊，說明這一情況痴柔。

F=type('Food', (), {remember2buy:'spam'})
E=type('Eggs', (F,), {remember2buy:'eggs'})
G=type('GoodFood', (F,E), {})

根據(jù)本地優(yōu)先級在調(diào)用G類對象屬性時應該優(yōu)先查找F類，但是在Python2.3之前的算法給出的順序是GEFO疫向，而在C3算法中通過阻止類層次不清晰的聲明來解決這一問題咳蔚，以上聲明在C3算法中就是非法的。

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算法的核心舌涨，是遞歸運算糯耍。

遍歷執(zhí)行merge操作的序列，如果一個序列的第一個元素，在其他序列中也是第一個元素温技，或不在其他序列出現(xiàn)啦租，則從所有執(zhí)行merge操作序列中刪除這個元素，合并到當前的mro中荒揣。merge操作后的序列篷角，遞歸地執(zhí)行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]

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

執(zhí)行merge操作的序列為[A,O]、[B,O]挂据、[A,B]以清。 A是序列[A,O]中的第一個元素，在序列[B,O]中不出現(xiàn)崎逃，在序列[A,B]中也是第一個元素掷倔，所以從執(zhí)行merge操作的序列([A,O]、[B,O]个绍、[A,B])中刪除A勒葱，合并到當前mro，[E]中巴柿。

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

再執(zhí)行merge操作凛虽，O是序列[O]中的第一個元素，但O在序列[B,O]中出現(xiàn)并且不是其中第一個元素广恢。繼續(xù)查看[B,O]的第一個元素B凯旋，B滿足條件，所以從執(zhí)行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]

Wiki有一個Python版本的C3算法:

def c3MRO(cls):
    if cls is object:
        # 討論假設頂層基類為object，遞歸終止
        return [object]

    # 構造C3-MRO算法的總式篷牌，遞歸開始
    mergeList = [c3MRO(baseCls) for baseCls in cls.__bases__]
    mergeList.append(list(cls.__bases__))
    mro = [cls] + merge(mergeList)
    return mro


def merge(inLists):
    if not inLists:
        # 若合并的內(nèi)容為空睡蟋，返回空list
        # 配合下文的排除空list操作，遞歸終止
        return []

    # 遍歷要合并的mro
    for mroList in inLists:
        # 取head
        head = mroList[0]
        # 遍歷要合并的mro（與外一層相同）枷颊，檢查尾中是否有head
        ### 此處也遍歷了被取頭的mro戳杀，嚴格地來說不符合標準算法實現(xiàn)
        ### 但按照多繼承中地基礎規(guī)則（一個類只能被繼承一次）该面，
        ### 頭不可能在自己地尾中，無影響信卡，若標準實現(xiàn)隔缀，反而增加開銷
        for cmpList in inLists[inLists.index(mroList) + 1:]:
            if head in cmpList[1:]:
                break
        else:
            # 篩選出好head
            nextList = []
            for mergeItem in inLists:
                if head in mergeItem:
                    mergeItem.remove(head)
                if mergeItem:
                    # 排除空list
                    nextList.append(mergeItem)
            # 遞歸開始
            return [head] + merge(nextList)
    else:
        # 無好head，引發(fā)類型錯誤
        raise TypeError

驗證上述算法的正確性傍菇，

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


print([i.__name__ for i in c3MRO(G)])
## ['G', 'E', 'A', 'F', 'B', 'C', 'object']

在Python3下猾瘸，如果想要查看繼承順序的話，更簡單丢习，每個類都有一個cls.mro()的方法牵触。比如上面的例子，直接執(zhí)行G.mro()就會打印mro list咐低。

例子2

再看一個復雜的例子：

class Type(type):
    def __repr__(cls):
        return cls.__name__

A = Type('A', (object,), {})
B = Type('B', (object,), {})
C = Type('C', (object,), {})
D = Type('D', (object,), {})
E = Type('E', (object,), {})
K1 = Type('K1', (A, B, C), {})
K2 = Type('K2', (D, B, E), {})
K3 = Type('K3', (D, A), {})
Z = Type('Z', (K1, K2,K3), {})

我們根據(jù)上面的繼承關系可以畫出繼承圖：

你可以嘗試著自己計算一下mro list揽思，當然，最后你需要用上面的算法或者class自帶的.mro()進行驗證见擦。

print(Z.mro()) # [Z, K1, K2, K3, D, A, B, C, E, <class 'object'>]

print([i.__name__ for i in c3MRO(Z)]) 
# ['Z', 'K1', 'K2', 'K3', 'D', 'A', 'B', 'C', 'E', 'object']

以上钉汗！

參考

Wiki百科——C3線性化

Python 2.3's use of C3 MRO

van Rossum, Guido. Method Resolution Order. The History of Python. 2010-06-23 [2018-01-18].