python中的MRO與多繼承

相關概念：

MRO：Method Resolution Order，即方法解析順序，是python中用于處理二義性問題的算法

二義性：

python支援多繼承，多繼承的語言往往會遇到以下兩類二義性的問題：

1. 有兩個基類A和B，A和B都定義了方法f()，C繼承A和B，那麼調用C的f()方法時會出現不确定。
2. 有一個基類A，定義了方法f()，B類和C類繼承了A類（的f()方法），D類繼承了B和C類，那麼出現一個問題，D不知道應該繼承B的f()方法還是C的f()方法。

C++也是支援多繼承的語言之一

1. 對于問題1，C++中通過同名覆寫的方式來解決，子類方法和屬性會優先調用，如果要在子類中通路被屏蔽的基類成員，應使用基類名來限定（BaseClassName::Func()）。
2. 對于問題2，C++中通過虛繼承來解決，以virtual關鍵字修飾共同的直接基類，進而保證不會産生多個基類副本産生歧義。

python中通過C3算法很好的避免了以上兩類二義性的情況。

深度優先算法（DFS，Depth-First-Search）

1. 把根節點壓入棧中。
2. 每次從棧中彈出一個元素，搜尋所有在它下一級的元素，把這些元素壓入棧中。并把這個元素記為它下一級元素的前驅。
3. 找到所要找的元素時結束程式。
4. 如果周遊整個樹還沒有找到，結束程式。

廣度優先算法（BFS，Breadth-First-Search）

1. 把根節點放到隊列的末尾。
2. 每次從隊列的頭部取出一個元素，檢視這個元素所有的下一級元素，把它們放到隊列的末尾。并把這個元素記為它下一級元素的前驅。
3. 找到所要找的元素時結束程式。
4. 如果周遊整個樹還沒有找到，結束程式。

拓撲排序：

對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是将G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u線上性序列中出現在v之前。通常，這樣的線性序列稱為滿足拓撲排序(TopologicalOrder)的序列，簡稱拓撲序列。

拓撲排序的實作步驟：

循環執行以下兩步，直到不存在入度為0的頂點為止

1. 選擇一個入度為0的頂點并輸出之；
2. 從網中删除此頂點及所有出邊。

python中調用父類方法的兩種方式：

class A(object):    def __init__(self):        self.name = "A: name"        print "A:__init__"    def fun(self):        print "A:fun" class B(A):    def __init__(self):        print "B:__init__"        A.__init__(self)                               # 使用類名直接調用        super(B, self).__init__()                # 使用super關鍵字調用    def fun(self):        print "B:fun"        A.fun(self)        super(B, self).fun()        print self.name

對于單繼承來說，上面這兩種方式并無本質上的差別，但是當出現多繼承的時候，super得到的基類就不一定是我們“認為”的基類了，我們看下面這個例子：

class A(object):    def __init__(self):        print "enter A"        print "leave A" class B(object):    def __init__(self):        print "enter B"        print "leave B" class C(A):    def __init__(self):        print "enter C"        super(C, self).__init__()        print "leave C" class D(A):    def __init__(self):        print "enter D"        super(D, self).__init__()        print "leave D" class E(B, C):    def __init__(self):        print "enter E"        B.__init__(self)        C.__init__(self)        print "leave E" class F(E, D):    def __init__(self):        print "enter F"        E.__init__(self)        D.__init__(self)        print "leave F" f = F()

輸出結果：

enter F

enter E

enter B

leave B

enter C

enter D

enter A

leave A

leave D

leave C

leave E

enter D

enter A

leave A

leave D

leave F

類的繼承關系如下所示：

   object

  |       \

  |        A

  |      / |

  B       C  D

   \   /   |

     E     |

       \   |

         F

我們的本意是希望調用構造函數的時候，對于基類的構造方法也進行調用，但是實際結果發現，A和D的構造函數被調用了2次，而且奇怪的是，當調用super(C, self).__init__()的時候，竟然進入D的構造函數，這也是為什麼D的構造函數被調用了兩次（一次是F調用的，一次是C調用的）！從繼承關系上看，C的基類應該是A才對。這就要引出下面要解釋的，python中的C3方法。不過針對上面這個例子，修改的思路很簡單，要麼全部使用類名來調用基類方法，要麼全部使用super()來調用，不要混用！

C3算法的演變曆史：

經典類（python 2.2之前）：

在python 2.2之前，python中使用經典類（classicclass），經典類是一種沒有繼承的類，所有類型都是type類型，如果經典類作為父類，子類調用父類構造函數會報錯。當時用作MRO的算法是DFS（深度優先），下面的例子是當時使用DFS算法的示例（向右是基類方向）：

1. 正常的繼承方式：

A->B->D

A->C->E

DFS的周遊順序為：A->B->D->C->E

這種情況下，不會産生問題。

1. 菱形的繼承方式

A->B->D

A->C->D

DFS的周遊順序為：A->B->D->C

對于這種情況，如果公共父類D中也定義了f()，C中重寫了方法f()，那麼C中的f()方法永遠也通路不到，因為按照周遊的順序始終先發現D中的f()方法，導緻子類無法重寫基類方法。

新式類（python2.2）：

在python2.2開始，為了使類的内置類型更加統一，引入了新式類（new-style class），新式類每個類都繼承自一個基類，預設繼承自object，子類可以調用基類的構造函數。由于所有類都有一個公共的祖先類object，是以新式類不能使用DFS作為MRO。在當時有兩種MRO并存：

如果是經典類，MRO使用DFS

如果是新式類，MRO使用BFS

針對新式類的BFS示例如下（向右是基類方向）：

1. 正常繼承方式：

A->B->D

A->C->E

BFS的周遊順序為：A->B->C->D->E

D是B的唯一基類，但是周遊時卻先周遊節點C，這種情況下應該先從唯一基類進行查找，這個原則稱為單調性。

1. 菱形的繼承方式

A->B->D

A->C->D

BFS的周遊順序為：A->B->C->D

BFS解決了前面提到的子類無法重寫基類方法的問題。

經典類和新式類并存（python2.3-python2.7），C3算法産生：

由于DFS和BFS針對經典類和新式類都有缺陷，從python2.3開始，引入了C3算法。針對前面兩個例子，C3算法的周遊順序如下：

1. 正常繼承方式：

A->B->D

A->C->E

C3的周遊順序為：A->B->D->C->E

1. 菱形的繼承方式

A->B->D

A->C->D

C3的周遊順序為：A->B->C->D

看起來是DFS和BFS的綜合，但是并非如此，下面的例子說明了C3算法的具體實作：

從前面拓撲排序的定義可知，将有向無環圖進行拓撲排序後，按照得到的拓撲序列周遊即可滿足單調性，原因是由根到葉即是子類到基類的方向，當基類的入度為0是，它就是子類的唯一基類，此時會優先周遊此基類，符合單調性。而子類無法重寫方法的問題也可以得到解決，因為當多個子類繼承自同一個基類時，該基類的入度不會先于子類減為0，是以可以保證優先周遊入度減為0的子類。

結合下面這張圖的例子來說明C3算法的執行步驟（圖中箭頭由子類指向父類）：

首先找入度為0的點，隻有A，把A取出，把A相關的邊去掉，再找下一個入度為0的點，B和C滿足條件，從左側開始取，取出B，這時順序是AB，然後去掉B相關的邊，這時候入度為0的點有E和C，依然取左邊的E，這時候順序為ABE，接着去掉E相關的邊，這時隻有一個點入度為0，那就是C，取C，順序為ABEC。去掉C的邊得到兩個入度為0的點D和F，取出D，順序為ABECD，然後去掉D相關的邊，那麼下一個入度為0的就是F，然後是object。是以最後的排序就為ABECDFobject。

了解了C3算法，我們前面那個混用的例子中調用super(C,self).__init__()會去調用D構造函數的原因也就顯而易見了。

在python中提供了__mro__内置屬性來檢視類的MRO，例如：

class D(object):    pass class E(object):    pass class F(object):    pass class C(D, F):    pass class B(E, D):    pass class A(B, C):    pass print A.__mro__ #輸出：(<class '__main__.A'>, <class '__main__.B'>, <class '__main__.E'>, <class '__main__.C'>, <class '__main__.D'>, <class '__main__.F'>, <type 'object'>)

參考連結：

二義性：http://baike.baidu.com/link?url=chZ4pXPmkAFI3nLMSi3LdIWV3iP7lOoHTcxkRnI3AgebLSFllRJH_WnGkGwVYvdQ2czM35DBLixOWI1IS8fL0XVZbKhBl-u5IBaCjfPgCaFjtI6SgK-RIlN3CteSYlC1

C++ 二義性問題：http://blog.csdn.net/whz_zb/article/details/6843298

C++中常見的兩種二義性問題及其解決方式：http://www.cnblogs.com/heimianshusheng/p/4836282.html

Python中Class類用法執行個體分析：http://www.jb51.net/article/74743.htm

廣度優先算法：http://baike.baidu.com/link?url=Jpp4QfrvgYlZEmfDAtFWyku1V77IKM0XZj8NjFUsCElWApCeA3sWIY61_Z-fS4PEUgirnOVBnPESxhgO3tEjNwYabJ684m-cjj7caIbdAEoEL7FoYexv7YQ0_AZIsUVMkgCQrZywDyAPwTcpV1RhJ_

深度優先算法：http://baike.baidu.com/item/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E7%AE%97%E6%B3%95

拓撲排序：http://baike.baidu.com/link?url=Ccrwv5pGeErmtnscpAMfDA6gp0c8GlT1jIaMD2HfyBSb9CaSXq96nYB_zXGJqbymLfWSkiJMgGHoRvOnuxjeAt0KwC72Lc79Y1GVFU7I5u0t6E-aquE9rqRvCBeWC1xv

拓撲排序的原理及其實作：http://blog.csdn.net/dm_vincent/article/details/7714519

python多繼承詳解：http://www.pythontab.com/html/2013/pythonhexinbiancheng_0828/550.html

你真的了解Python中MRO算法嗎：http://python.jobbole.com/85685/