Python的多繼承問題-MRO和C3算法

作者:

Python 中的方法解析順序（Method Resolution Order, MRO）定義了多繼承存在時 Python 解釋器查找函數解析的正確方式。當 Python 版本從 2.2 發展到 2.3 再到現在的 Python 3，MRO算法也隨之發生了相應的變化。這種變化在很多時候影響了我們使用不同版本 Python 編程的過程。

大部分內容轉載自C3 線性化算法與 MRO 理解Python中的多繼承

什麼是 MRO

MRO 全稱方法解析順序（Method Resolution Order）。它定義了 Python 中多繼承存在的情況下，解釋器查找函數解析的具體順序。什麼是函數解析順序？我們首先用一個簡單的例子來說明。請仔細看下面代碼：

class A():
    def who_am_i(self):
        print("I am A")
        
class B(A):
    pass
        
class C(A):
    def who_am_i(self):
        print("I am C")

class D(B,C):
    pass
    
d = D()

如果我問在 Python 2 中使用 D 的實例調用 d.who_am_i()，究竟執行的是 A 中的 who_am_i() 還是 C 中的 who_am_i()，我想百分之九十以上的人都會不假思索地回答：肯定是 C 中的 who_am_i()，因為 C 是 D 的直接父類。然而，如果你把代碼用 Python 2 運行一下就可以看到 d.who_am_i() 打印的是 I am A。

是不是覺得很混亂很奇怪？感到奇怪就對了！！！

這個例子充分展示了 MRO 的作用：決定基類中的函數到底應該以什麼樣的順序調用父類中的函數。可以明確地說，Python 發展到現在，MRO 算法已經不是一個憑藉著執行結果就能猜出來的算法了。如果沒有深入到 MRO 算法的細節，稍微複雜一點的繼承關係和方法調用都能徹底繞暈你。

New-style Class vs. Old-style Class

在介紹不同版本的 MRO 算法之前，我們有必要簡單地回顧一下 Python 中類定義方式的發展歷史。儘管在 Python 3 中已經廢除了老式的類定義方式和 MRO 算法，但對於仍然廣泛使用的 Python 2 來說，不同的類定義方式與 MRO 算法之間具有緊密的聯繫。了解這一點將幫助我們從 Python 2 向 Python 3 遷移時不會出現莫名其妙的錯誤。

在 Python 2.1 及以前，我們定義一個類的時候往往是這個樣子（我們把這種類稱為 old-style class)：

class A:
    def __init__(self):
        pass

Python 2.2 引入了新的模型對象（new-style class），其建議新的類型通過如下方式定義：

class A(object):
    def __init__(self):
        pass

注意后一種定義方式显示註明類 A 繼承自 object。Python 2.3 及後續版本為了保持向下兼容，同時提供以上兩種類定義用以區分 old-style class 和 new-style class。Python 3 則完全廢棄了 old-style class 的概念，不論你通過以上哪種方式書寫代碼，Python 3 都將明確認為類 A 繼承自 object。這裏我們只是引入 old-style 和 new-style 的概念，如果你對他們的區別感興趣，可以自行看 stackoverflow 上有關該問題的解釋。

理解 old-style class 的 MRO

我們使用前文中的類繼承關係來介紹 Python 2 中針對 old-style class 的 MRO 算法。如果你在前面執行過那段代碼，你可以看到調用 d.who_am_i() 打印的應該是 I am A。為什麼 Python 2 的解釋器在確定 D 中的函數調用時要先搜索 A 而不是先搜索 D 的直接父類 C 呢？

這是由於 Python 2 對於 old-style class 使用了非常簡單的基於深度優先遍歷的 MRO 算法（關於深度優先遍歷，我想大家肯定都不陌生）。當一個類繼承自多個類時，Python 2 按照從左到右的順序深度遍歷類的繼承圖，從而確定類中函數的調用順序。這個過程具體如下：

  1. 檢查當前的類裏面是否有該函數，如果有則直接調用。
  2. 檢查當前類的第一個父類裏面是否有該函數，如果沒有則檢查父類的第一個父類是否有該函數，以此遞歸深度遍歷。
  3. 如果沒有則回溯一層，檢查下一個父類裏面是否有該函數並按照 2 中的方式遞歸。

上面的過程與標準的深度優先遍歷只有一點細微的差別：步驟 2 總是按照繼承列表中類的先後順序來選擇分支的遍歷順序。具體來說，類 D 的繼承列表中類順序為 B, C，因此，類 D 按照先遍歷 B 分支再遍歷 C 分支的順序來確定 MRO。

我們繼續用第一個例子中的函數繼承圖來說明這個過程：

按照上述深度遞歸的方式，函數 d.who_am_i() 調用的搜索順序是 D, B, A, C, A。由於一個類不能兩次出現，因此在搜索路徑中去除掉重複出現的 A，得到最終的方法解析順序是 D, B, A, C。這樣一來你就明白了為什麼 d.who_am_i() 打印的是 I am A 了。

在 Python 2 中，我們可以通過如下方式來查看 old-style class 的 MRO：

>>> import inspect
>>> inspect.getmro(D)

理解 new-style class 的 MRO

從上面的結果可以看到，使用深度優先遍歷的查找算法並不合理。因此，Python 3 以及 Python 2 針對 new-style class 採用了新的 MRO 算法。如果你使用 Python 3 重新運行一遍上述腳本，你就可以看到函數 d.who_am_i() 的打印結果是 I am C。

>>> d.who_am_i()
I am C
>>> D.__mro__
(<class 'test.D'>, <class 'test.B'>, <class 'test.C'>, <class 'test.A'>, <class 'object'>)

新算法與基於深度遍歷的算法類似，但是不同在於新算法會對深度優先遍歷得到的搜索路徑進行額外的檢查。其從左到右掃描得到的搜索路徑，對於每一個節點解釋器都會判斷該節點是不是好的節點。如果不是好的節點，那麼將其從當前的搜索路徑中移除。

那麼問題在於，什麼是一個好的節點？我們說 N 是一個好的節點當且僅當搜索路徑中 N 之後的節點都不繼承自 N。我們還以上述的類繼承圖為例，按照深度優先遍歷得到類 D 中函數的搜索路徑 D, B, A, C, A。之後 Python 解釋器從左向右檢查時發現第三個節點 A 不是一個好的節點，因為 A 之後的節點 C 繼承自 A。因此其將 A 從搜索路徑中移除，然後得到最後的調用順序 D, B, C, A。

採用上述算法，D 中的函數調用將優先查找其直接父類 B 和 C 中的相應函數。

C3線性化算法

上一小結我們從直觀上概述了針對 new-style class 的 MRO 算法過程。事實上這個算法有一個明確的名字 C3 linearization。下面我們給出其形式化的計算過程。

上面的過程看起來好像很複雜，我們用一個例子來具體執行一下，你就會覺得其實還是挺簡單的。假設我們有如下的一個類繼承關係：

參考來源：Understanding Python MRO – Class search path

class X():
    def who_am_i(self):
        print("I am a X")
        
class Y():
    def who_am_i(self):
        print("I am a Y")
        
class A(X, Y):
    def who_am_i(self):
        print("I am a A")
        
class B(Y, X):
     def who_am_i(self):
         print("I am a B")
         
class F(A, B):
    def who_am_i(self):
        print("I am a F")


Traceback (most recent call last):
  File "test.py", line 17, in <module>
    class F(A, B):
TypeError: Cannot create a consistent method resolution
order (MRO) for bases X, Y

為什麼採用C3算法

上圖中都是使用BFS算法來尋找繼承鏈，但是都會有問題，左邊的繼承模式會違背單調性的原則，右邊的棱形繼承鏈，如果是C重寫了繼承於A的方法，B沒有，但是根據MRO繼承鏈，最終調用的都是A類的方法，C中實現的方法永遠不會被調用，這些都是再python2的問題，python引入C3算法后就解決了這些問題。

C3算法最早被提出是用於Lisp的，應用在Python中是為了解決原來基於深度優先搜索算法不滿足本地優先級，和單調性的問題。
本地優先級：指聲明時父類的順序，比如C(A,B)，如果訪問C類對象屬性時，應該根據聲明順序，優先查找A類，然後再查找B類。
單調性：如果在C的解析順序中，A排在B的前面，那麼在C的所有子類里，也必須滿足這個順序。

在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之前的算法給出的順序是G E F O，而在心得C3算法中通過阻止類層次不清晰的聲明來解決這一問題，以上聲明在C3算法中就是非法的。

小結

C3算法的核心 ：

  1. 遍歷執行merge操作的序列，如果一個序列的第一個元素，在其他序列中也是第一個元素，或不在其他序列出現，則從所有執行merge操作序列中刪除這個元素，合併到當前的mro中。

  2. merge操作后的序列，繼續執行merge操作，直到merge操作的序列為空。

  3. 如果merge操作的序列無法為空，則說明不合法。

參考資料

理解Python中的多繼承-C3 線性化算法

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

Deep Thoughts by Raymond Hettinger

C3 linearization

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※超省錢租車方案

※別再煩惱如何寫文案,掌握八大原則!

※回頭車貨運收費標準

※教你寫出一流的銷售文案?

※FB行銷專家,教你從零開始的技巧