python多重繼承新算法C3介紹

mro即 method resolution order (方法解釋順序)，主要用于在多繼承時判斷屬性的路徑(來自于哪個類)。

在python2.2版本中，算法基本思想是根據每個祖先類的繼承結構，編譯出一張列表，包括搜索到的類，按策略刪除重復的。但是，在維護單調性方面失敗過（順序保存），所以從2.3版本，采用了新算法C3。

為什么采用C3算法

C3算法最早被提出是用于Lisp的，應用在Python中是為了解決原來基于深度優(yōu)先搜索算法不滿足本地優(yōu)先級，和單調性的問題。

本地優(yōu)先級：指聲明時父類的順序，比如C(A,B)，如果訪問C類對象屬性時，應該根據聲明順序，優(yōu)先查找A類，然后再查找B類。

單調性：如果在C的解析順序中，A排在B的前面，那么在C的所有子類里，也必須滿足這個順序。

C3算法

判斷mro要先確定一個線性序列，然后查找路徑由由序列中類的順序決定。所以C3算法就是生成一個線性序列。

如果繼承至一個基類:

代碼如下:

class B(A)

這時B的mro序列為[B,A]

如果繼承至多個基類

代碼如下:

class B(A1,A2,A3 ...)

這時B的mro序列 mro(B) = [B] + merge(mro(A1), mro(A2), mro(A3) ..., [A1,A2,A3])
merge操作就是C3算法的核心。

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

merge操作后的序列，繼續(xù)執(zhí)行merge操作，直到merge操作的序列為空。

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

例子：
代碼如下:

class A(O):pass
class B(O):pass
class C(O):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]中不出現，在序列[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]中出現并且不是其中第一個元素。繼續(xù)查看[B,O]的第一個元素B，B滿足條件，所以從執(zhí)行merge操作的序列中刪除B，合并到[E, A]中。
代碼如下:

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

實現C3算法的代碼

代碼如下:

#-*- encoding:GBK -*-#
def mro_C3(*cls):
if len(cls)==1:
if not cls[0].__bases__:
return cls
else:
return cls+ mro_C3(*cls[0].__bases__)
else:
seqs = [list(mro_C3(C)) for C in cls ] +[list(cls)]
res = []
while True:
non_empty = list(filter(None, seqs))
if not non_empty:
return tuple(res)
for seq in non_empty:
candidate = seq[0]
not_head = [s for s in non_empty if candidate in s[1:]]
if not_head:
candidate = None
else:
break
if not candidate:
raise TypeError("inconsistent hierarchy, no C3 MRO is possible")
res.append(candidate)
for seq in non_empty:
if seq[0] == candidate:
del seq[0]

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯(lián)系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com