python3的C3算法

一、基本概念

1. mro序列

MRO是一個有序清單L，在類被建立時就計算出來。

通用計算公式為：

mro(Child(Base1，Base2)) = [ Child ] + merge( mro(Base1), mro(Base2),  [ Base1, Base2] )
（其中Child繼承自Base1, Base2）
           

如果繼承至一個基類：class B(A) 

這時B的mro序列為

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

如果繼承至多個基類：class B(A1, A2, A3 …) 

這時B的mro序列

mro(B)  = mro( B(A1, A2, A3 …) )
= [B] + merge( mro(A1), mro(A2), mro(A3) ..., [A1, A2, A3] )
= ...
           

計算結果為清單，清單中至少有一個元素即類自己，如上述示例[A1,A2,A3]。merge操作是C3算法的核心。

2. 表頭和表尾：

表頭： 清單的第一個元素

表尾： 清單中表頭以外的元素集合（可以為空）

示例 

清單：[A, B, C] 

表頭是A，表尾是B和C

3. 清單之間的+操作

+操作：

[A] + [B] = [A, B]
（以下的計算中預設省略）
           

3. merge操作：

merge操作流程圖： 

merge操作示例：

如計算merge( [E,O], [C,E,F,O], [C] )
有三個清單 ：  ①      ②          ③

1 merge不為空，取出第一個清單清單①的表頭E，進行判斷                              
   各個清單的表尾分别是[O], [E,F,O]，E在這些表尾的集合中，因而跳過目前目前清單
2 取出清單②的表頭C，進行判斷
   C不在各個清單的集合中，因而将C拿出到merge外，并從所有表頭删除
   merge( [E,O], [C,E,F,O], [C]) = [C] + merge( [E,O], [E,F,O] )
3 進行下一次新的merge操作 ......      

二、執行個體

1. 計算執行個體1

示例：（多繼承UML圖，引用見參考） 

備注：O==object

如何計算mro(A) ？

mro(A) = mro( A(B,C) )

原式= [A] + merge( mro(B),mro(C),[B,C] )

  mro(B) = mro( B(D,E) )
         = [B] + merge( mro(D), mro(E), [D,E] )  # 多繼承
         = [B] + merge( [D,O] , [E,O] , [D,E] )  # 單繼承mro(D(O))=[D,O]
         = [B,D] + merge( [O] , [E,O]  ,  [E] )  # 拿出并删除D
         = [B,D,E] + merge([O] ,  [O])
         = [B,D,E,O]

  mro(C) = mro( C(E,F) )
         = [C] + merge( mro(E), mro(F), [E,F] )
         = [C] + merge( [E,O] , [F,O] , [E,F] )
         = [C,E] + merge( [O] , [F,O]  ,  [F] )  # 跳過O，拿出并删除
         = [C,E,F] + merge([O] ,  [O])
         = [C,E,F,O]

原式= [A] + merge( [B,D,E,O], [C,E,F,O], [B,C])
    = [A,B] + merge( [D,E,O], [C,E,F,O],   [C])
    = [A,B,D] + merge( [E,O], [C,E,F,O],   [C])  # 跳過E
    = [A,B,D,C] + merge([E,O],  [E,F,O])
    = [A,B,D,C,E] + merge([O],    [F,O])  # 跳過O
    = [A,B,D,C,E,F] + merge([O],    [O])
    = [A,B,D,C,E,F,O]
      

2. 執行個體代碼測試

對于以上計算，用代碼來測試。

class D: pass
class E: pass
class F: pass
class B(D,E): pass
class C(E,F): pass
class A(B,C): pass

print("從A開始查找：")
for s in A.__mro__:
    print(s)

print("從B開始查找：")
for s in B.__mro__:
    print(s)

print("從C開始查找：")
for s in C.__mro__:
    print(s)      

結果：

從A開始查找：
<class '__main__.A'>
<class '__main__.B'>
<class '__main__.D'>
<class '__main__.C'>
<class '__main__.E'>
<class '__main__.F'>
<class 'object'>
從B開始查找：
<class '__main__.B'>
<class '__main__.D'>
<class '__main__.E'>
<class 'object'>
從C開始查找：
<class '__main__.C'>
<class '__main__.E'>
<class '__main__.F'>
<class 'object'>      

三、總結

每次判斷如何讀取都要這麼麻煩計算嗎？可有簡單方法？

我對此做了一個簡單總結。

1. 規律總結

如何快速判斷查找規律？

從 “目前子類” 向上查找它的父類，

若 “目前子類” 不是 “查找的父類” 的最後一個繼承的子類時，則跳過該 “查找的父類” 的查找，開始查找 “目前子類” 的下一個父類

查找規律流程圖：

2. 規律測試

執行個體2：

對于如下繼承： 

通過如下判斷模式：

代碼測試：

class A1: pass
class A2: pass
class A3: pass
class B1(A1,A2): pass
class B2(A2): pass
class B3(A2,A3): pass
class C1(B1): pass
class C2(B1,B2): pass
class C3(B2,B3): pass
class D(C1, C2, C3): pass

print("從D開始查找：")
for s in D.__mro__:
    print(s)

print("從C3開始查找：")
for s in C3.__mro__:
    print(s)      

結果：

從D開始查找：
<class '__main__.D'>
<class '__main__.C1'>
<class '__main__.C2'>
<class '__main__.B1'>
<class '__main__.A1'>
<class '__main__.C3'>
<class '__main__.B2'>
<class '__main__.B3'>
<class '__main__.A2'>
<class '__main__.A3'>
<class 'object'>
從C3開始查找：
<class '__main__.C3'>
<class '__main__.B2'>
<class '__main__.B3'>
<class '__main__.A2'>
<class '__main__.A3'>
<class 'object'>      

　　

　　

　　

　　

轉載于:https://www.cnblogs.com/pyedu/p/10389307.html