引子：

如圖反映了python3中，幾個(gè)類的繼承關(guān)系和查找順序。對于類A，其查找順序?yàn)?#xff1a;A,B,E,C,F,D,G,(Object)，這并不是一個(gè)簡單的深度優(yōu)先或廣度優(yōu)先的規(guī)律。那么這個(gè)順序到底是如何產(chǎn)生的？

C3線性是用于獲取多重繼承下繼承順序的一種算法。通常，被稱為方法解析順序，即MRO(method resolution order)。

算法的名字“C3”并不是縮寫，而是指該算法的三大重要屬性：

1.前趨圖。作為有向無環(huán)圖，找不到任何的循環(huán)，通常用前趨圖來理解程序的依賴關(guān)系。

2.保持局部的優(yōu)先次序。

3.單調(diào)性。

C3是1996年首次被提出。在python2.3及后續(xù)版本中，C3被選定為默認(rèn)的解析算法。

一個(gè)類的C3線性表，是由兩部分進(jìn)行merge操作得到的，第一部分是是它所有父類的C3線性表(parents' linearizations)，第二部分是它所有父類組成的列表(parents list)。后者其實(shí)是局部的優(yōu)先級列表。

所謂merge操作，遵循以下原則：表的首個(gè)元素不可以出現(xiàn)在其他地方，如果出現(xiàn)了這樣的情形，那么就要將該元素全部移出，放到產(chǎn)出列表(output list)中。如果循環(huán)進(jìn)行這一操作，就可以把所有的表逐步移出，逐步擴(kuò)張產(chǎn)出表，最后得到一個(gè)純粹的產(chǎn)出表。這個(gè)產(chǎn)出表就是最后的C3線性表。

舉個(gè)例子：

python3代碼：

class O:

pass

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

即：

O從以下類繼承：無(實(shí)際上python3中默認(rèn)為object類，因?yàn)樗蓄惱^承于object類，所以才有多種多樣的內(nèi)置方法可用)

A從以下類繼承：O

B從以下類繼承：O

C從以下類繼承：O

D從以下類繼承：O

E從以下類繼承：O

K1從以下類繼承：A,B,C

K2從以下類繼承：D,B,E

K3從以下類繼承：D,A

Z從以下類繼承：K1,K2,K3

為方便起見，記類cls的線性表為L[cls]。

首先，從最簡單的類O開始：

L[O]：平凡的情形，直接定為列表[O]，即線性表的第一項(xiàng)是自身。所以，L[0]=[O]

L[A]：類A的所有父類是O，所以前一部分是L[O]，后一部分是類A所有父類列表[O]，前面已經(jīng)得出L[O]=[O]，因此L[A] = [A] + merge(L[O] + [O]) = [A]+merge([O] + [O]) = [A] + [O] = [A,O]

同理:

L[B]=[B,O]

L[C]=[C,O]

L[D]=[D,O]

L[E]=[E,O]

L[K1]：線性表第一項(xiàng)為自身K1，以后的項(xiàng)為其所有父類C3線性表和其所有父類列表的并——

K1繼承于A,B,C，所以所有父類C3線性表為：L[A],L[B],L[C]；所有父類列表為：A,B,C。

并起來就是merge(L[A],L[B],L[C],A,B,C)，然后，遵循原則一步步將其拆開。

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只在這些列表的首項(xiàng)出現(xiàn)(如：[A,O]和[A,B,C])，應(yīng)當(dāng)把它移除到產(chǎn)出列表(output list)。

=[K1,A]+merge([O],[B,O],[C,O],[B,C])——元素O在列表的首項(xiàng)出現(xiàn)過(如：[O])，也在有些列表的剩余項(xiàng)出現(xiàn)過(如[B,O],[C,O])，所以保留它。但是，元素B只在這些列表的首項(xiàng)出現(xiàn)(如：[B,O],[B,C])，應(yīng)當(dāng)移出它。

=[K1,A,B]+merge([O],[O],[C,O],[C])——移出B后，同理發(fā)現(xiàn)C也是要移出的

=[K1,A,B,C]+merge([O],[O],[O])——merge操作已經(jīng)走到盡頭了

=[K1,A,B,C,O]

L[K2]：K2繼承于D,B,E，所以所有父類C3線性表為L[D],L[B],L[E]，所有父類列表為D,B,E。同理可得：

L[K2]=[K2]+merge([D,O],[B,O],[C,O],[D,B,E])

=[K2,D]+merge([O],[B,O],[C,O],[B,E])

=[K2,D,B]+merge([O],[O],[C,O],[E])

=[K2,D,B,E]+merge([O],[O],[O],[O])

=[K2,D,B,E,O]

L[K3]：K3繼承于D,A，所以所有父類的C3線性表為L[D],L[A]，所有父類列表為D,A。同理可得：

L[K3]=[K3,D,A,O]

L[Z]：Z繼承于K1,K2,K3。前面計(jì)算了K1,K2,K3的線性表，所以這里直接代入計(jì)算：

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])——應(yīng)移出K1

=[Z,K1]+merge([A,B,C,O],[K2,D,B,E,O],[K3,D,A,O],[K2,K3])——應(yīng)移出K2

=[Z,K1,K2]+merge([A,B,C,O],[D,B,E,O],[K3,D,A,O],[K3])——應(yīng)移出K3

=[Z,K1,K2,K3]+merge([A,B,C,O],[D,B,E,O],[D,A,O])——應(yīng)移出D

=[Z,K1,K2,K3,D]+merge([A,B,C,O],[B,E,O],[A,O])——應(yīng)移出A

=[Z,K1,K2,K3,D,A]+merge([B,C,O],[B,E,O],[O])——應(yīng)移出B

=[Z,K1,K2,K3,D,A,B]+merge([C,O],[E,O],[O])——應(yīng)移出C

=[Z,K1,K2,K3,D,A,B,C]+merge([O],[E,O],[O])——應(yīng)移出E

=[Z,K1,K2,K3,D,A,B,C,E]+merge([O],[O],[O])——耗盡，結(jié)束

=[Z,K1,K2,K3,D,A,B,C,E,O]

在python3中使用對類help()函數(shù)，可以很方便地查看MRO：

可以看出，python3中的MRO計(jì)算，不能以簡單地找完一層再找上一層。假如以“廣度優(yōu)先、從左到右、絕不重復(fù)”這一規(guī)律概括，很容易誤認(rèn)為按照如下順序查找：

Z從K1，K2，K3繼承，所以前三項(xiàng)為K1，K2，K3。接下來找K1的父類A，B，C。再找K2的父類D，B，E，再找K3的父類D，A。但是這樣就造成重復(fù)。為防止重復(fù)，還得定義其他規(guī)范。

最后，利用python實(shí)現(xiàn)mro的生成。代碼可用，但是用了遞推函數(shù)，有機(jī)會以生成器的方式優(yōu)化防止棧溢出。

1 defnot_in_tail(t, L):2 #判斷一個(gè)元素是不是在一個(gè)列表的尾巴中出現(xiàn)過。如果從未出現(xiàn)，返回真。

3 if notL:4 returnTrue5 if len(L) == 1:6 returnTrue7 if t in L[1:]:8 returnFalse9 else:10 returnTrue11

12

13 defmro(cls):14 #如果一個(gè)類沒有任何父類，那么它的線性表里只有它自己。其實(shí)這個(gè)類就是object

15 if not cls.__bases__:16 return[cls, ]17 #如果一個(gè)類只有一個(gè)父類object，那么它的線性表里是先找它自己，再找object

18 if cls.__bases__ ==(object,):19 return[cls, object]20 #output用于產(chǎn)出線性表，第一項(xiàng)肯定是該類自己。

21 output =[cls, ]22 #這里使用遞歸方法，拿到它所有父類的線性表。后一項(xiàng)為所有父類的列表。

23 merge = [mro(parent) for parent in cls.__bases__] + [list(cls.__bases__), ]24 whileTrue:25 #merge操作過程中會不斷地把元素取出，可能會有子列表被取空，這時(shí)候應(yīng)直接刪除

26 while [] inmerge:27 merge.remove([])28 #merge操作的終極目標(biāo)，就是全部剩下object，這就是while的終止條件

29 if all([t == [object, ] for t inmerge]):30 merge =[object, ]31 break

32 #準(zhǔn)備將欲取出的元素放在head中。該行是一個(gè)變量初始化。

33 head =None34 #遍歷所有的子列表，同時(shí)還要拿到索引。

35 for index, sublist inenumerate(merge):36 #如果當(dāng)前子列表只有object，那么就跳過

37 if sublist ==[object, ]:38 continue

39 #判斷子列表的第一項(xiàng)是否滿足條件：從未在任何列表的尾巴中出現(xiàn)。如果滿足此條件，記下此元素，退出循環(huán)準(zhǔn)備刪除

40 if all([not_in_tail(sublist[0], l) for l inmerge[index:]]):41 head =sublist[0]42 break

43 ifhead:44 #將該元素添加到線性表中

45 output.append(head)46 #將該元素從所有子列表中刪除

47 for l inmerge:48 if head inl:49 l.remove(head)50 #從最終返回的列表可以看出產(chǎn)生線性表的兩部分結(jié)構(gòu)。merge的終極目標(biāo)就是只剩下[object,]，補(bǔ)上即可

51 mro_list = output +[object, ]52 returnmro_list53

54 # 以下是測試用例

55 classO:56 pass

57

58

59 classA(O):60 pass

61

62

63 classB(O):64 pass

65

66

67 classC(O):68 pass

69

70

71 classD(O):72 pass

73

74

75 classE(O):76 pass

77

78

79 classK1(A, B, C):80 pass

81

82

83 classK2(D, B, E):84 pass

85

86

87 classK3(D, A):88 pass

89

90

91 classZ(K1, K2, K3):92 pass

93

94

95 print(mro(Z))96

97 print(mro(O))

輸出結(jié)果為：

1 [, , , , , , , , , , ]2

3 [, ]

可以通過__mro__方法驗(yàn)證：

1 print(Z.__mro__)2

3 (, , , , , , , , , , )

當(dāng)然，__mro__方法返回的是元組。所以前面的python代碼可以利用tuple()改成以元組形式返回。在遞推時(shí)，加一層list()以元組形式傳入。不再展開。

回到開頭的引子。經(jīng)過驗(yàn)證，答案完全正確：

class G:pass

class E(G):pass

class B(E):pass

class F(G):pass

class C(F):pass

class D(G):pass

class A(B,C,D):pass

print(mro(A))print(A.__mro__)

[, , , , , , , ]

(, , , , , , , )

總結(jié)

以上是生活随笔為你收集整理的mro python_用python实现MRO算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。