C3 算法:Python 多重继承的内部原理

栏目: IT技术 · 发布时间: 4年前

内容简介:在 Python 中使用 Mixin 有没有遇到过TLDR; 我个人觉得 C3 算法就是拓扑排序…考虑下面的多重继承的代码:

Python 中使用 Mixin 有没有遇到过 Cannot create a consistent method resolution 错误?Mixin 在 Python 里只是多重继承(multiple inheritance) 的一种用法,而多重继承时,Python 是如何决定父类的顺序呢?咱们就来看看 C3 算法是何方神圣。

TLDR; 我个人觉得 C3 算法就是拓扑排序…

Method Resolution Order(MRO)

考虑下面的多重继承的代码:

class A(object):
    def hello(self):
        print("hello from A")

class B(object):
    def hello(self):
        print("hello from A")

class C(A, B): pass

C().hello()

上面的 C().hello() 输出是什么呢?这里会输出 hello from A

Python 的多重继承符合直觉,可以认为:在查找一个方法或类时, 会从左到右查找父类的方法或类 ,找到为止。这个查找顺序叫作 Method Resolution Order,简称 MRO。可以通过 <class>.mro() 查看,如:

>>> C.mro()
[__main__.C, __main__.A, __main__.B, object]

可以看出,查找方法时,会先查 A 再查 B。

C3 算法

那么如何计算 MRO 呢?Python 里使用 C3 算法。其实就是拓扑排序,只是 排序 的“图”上加了点特技。

符号定义:

  • 方便起见,先定义符号 $C_1C_2…C_N$ 代表一个列表 $[C_1, C_2, …, C_N]$
  • 再定义加号: $C + (C_1 C_2 … C_N) = C C_1 C_2 … C_N$
  • 定义 $C_1C_2…C_N$ 列表中,$C_1$ 为头部,$C_2…C_N$ 为尾部

算法:

  • 对于类定义 class C(B1, B2, ..., BN) ,记它的 MRO 为 L[C] (L 代表 linearization)
  • 所有类都会继承 object ,定义 L[object] = object
  • 算法定义计算步骤为 $L[C] = C + merge(L[B_1], L[B_2], …, L[B_N], B_1B_2…B_N)$
    • 注意这里末尾的 $B_1B_2…B_N$,就是我们说的“特技”
  • merge 方法定义为:
    1. 选取第一个列表 $B_1$
    2. 首先选取第一个列表 $B_1$ 第一个元素
    3. 如果该元素不出现在 merge 方法其它列表的尾部,则输出元素,并将该元素从其它列表中移除,取下一个元素
    4. 如果该元素出现在其它列表的尾部,则选取下一个列表,并重复步骤 2,直到所有列表为空
    5. 如果遍历过所有的列表,有列表不为空且过程中没有输出,则说明得不到有效 MRO,报错

算法示例

merge 算法其实就是拓扑排序,举例如下:

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

继承关系如下图左,而预期的 MRO 关系如下图右(A->B 表示 MRO 中 A 出现在 B 之前):

C3 算法:Python 多重继承的内部原理

计算 MRO 相当于对上右图做拓扑排序,merge 参数的最后一项,实际定义了同层元素间的指向。

Level 2 的 MRO 很容易计算

L[E] = E + merge(L[O]) = E + merge(O) = E + O = EO
L[D] = D + merge(L[O]) = D + merge(O) = D + O = DO
L[F] = F + merge(L[O]) = F + merge(O) = F + O = FO

Level 1 的 MRO 计算如下:

L[B] = B + merge(L[E], L[D], ED)
     = B + merge(EO, DO, ED)     # 检测 EO 中的元素 E
     = B + E + merge(O, DO, D)   # 检测 DO 中的元素 D
     = B + E + D +merge(O, O, ) # 检测元素 O
     = B + E + D +O
     = BEDO

L[C] = C + merge(L[D], L[F], DF)
     = B + merge(DO, FO, DF)     # 检测 DO 中的元素 D
     = B + D + merge(O, FO, F)   # 检测 FO 中的元素 F
     = B + D + F + merge(O, O, ) # 检测元素 O
     = B + D + F + O
     = BDFO

于是 A 的 MRO 为:

L[A] = A + merge(L[B], L[C], BC)
     = A + merge(BEDO, BDFO, BC)              # 检测 BEDO 中的 B
     = A + B + merge(EDO, DFO, C)             # 检测 EDO 中的 E
     = A + B + E + merge(DO, DFO, C)          # 检测 DO 中的 D
     = A + B + E + D + merge(O, FO, C)        # 检测 O 中的 O,出现在 FO 尾部
     = A + B + E + D + merge(O, FO, C)        # 检测 C 中的 C
     = A + B + E + D + C + merge(O, FO, )     # 检测 O 中的 O,出现在 FO 尾部
     = A + B + E + D + C + merge(O, FO, )     # 检测 FO 中的 F
     = A + B + E + D + C + F +merge(O, O, )  # 检测 O
     = A + B + E + D + C + F +O
     = ABEDCFO

最后注意根据拓扑图,元素 E 和 C 的顺序先后其实无关紧要。

反例

对于下面的类定义,算法就会报错。因为 A 要求 X 在 Y 左边,而 B 的要求正好相反,二者矛盾。

O = object
class X(O): pass
class Y(O): pass
class A(X,Y): pass
class B(Y,X): pass
class T(A,B): pass

拓扑图如下,我们发现它存在循环引用:

C3 算法:Python 多重继承的内部原理

算法计算过程如下:

L[X] = XO
L[Y] = YO
L[A] = A + merge(L[X], L[Y], XY)
     = A + merge(XO, YO, XY)
     = AXYO
L[B] = B + merge(L[Y], L[X], XY)
     = B + merge(YO, XO, YX)
     = BYXO
L[T] = T + merge(L[A], L[B], AB)
     = T + merge(AXYO, BYXO, AB)        # 检测 AXYO 中的 A
     = T + A + merge(XYO, BYXO, B)      # 检测 XYO 中的 X,出现在 BYXO 的尾部,跳过
     = T + A + merge(XYO, BYXO, B)      # 检测 BYXO 中的 B
     = T + A + B + merge(XYO, YXO, )    # 检测 YXO 中的 Y,出现在 XYO 的尾部
     # 此处无法再化简,报错

Python 2.3 之前的问题

C3 算法是在 Python 2.3 后引入的,在这之前,考虑下面的示例:

F=type('Food',(),{'remember2buy':'spam'})
E=type('Eggs',(F,),{'remember2buy':'eggs'})
G=type('GoodFood',(F,E),{}) # works before Python 2.3

用 C3 的方式画出拓扑图如下,虽然代码里不明显,图里可以看到存在循环引用:

C3 算法:Python 多重继承的内部原理

而 Python 2.3 之前的 MRO 算法在调用 G.remember2buy 属性时,预期输出 spam (因为 G(F, E) ,预期先查找 F 的方法),而实际会输出 eggs (E 的方法),不符合预期。Python 2.3 及以后就会报错。

因此如果在实现 Mixin 的时候,如果搞错顺序可能就无法运行,例如:

class Base(object): pass
class MixinA(Base): pass
class MixinB(Base): pass
class Y(MixinA, MixinB, Base): pass
class X(Base, MixinA, MixinB): pass # error

简单的结论是越具体的实现位置越靠前。

小结

写到最后发现:C3 算法似乎和拓扑排序没有任何区别?只是在标记拓扑图上做一些工夫,保证类定义的先后顺序反映在 MRO 中:即 A(B, C) 最后的 MRO 中 B 一定在 C 之前。

这个知识也许在使用 mixin 出错的时候能帮上忙,剩余时候感觉也没什么用。


以上所述就是小编给大家介绍的《C3 算法:Python 多重继承的内部原理》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

编程精粹

编程精粹

Steve Maguire / 人民邮电出版社 / 2009.2 / 45.00元

编写高质量的、没有bug的程序,是每位程序员所追求的目标。但随着软件规模越来越大,功能日趋复杂,这一目标变得越来越困难。 本书揭示了微软公司应对质量挑战、开发出世界级代码的技术内幕,作者在自己不断探索、实践和思考的基础上,系统总结了多年来指导微软各团队的经验,将其凝聚为许多切实可行的编程实践指导,可谓字字珠玑。正因如此,本书被公认为与《代码大全》齐名的编程技术名著,曾于1993年荣获有软件开......一起来看看 《编程精粹》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具