时间戳

首页 > 解决方案 > python中mro的C3算法如何工作？

python - python中mro的C3算法如何工作？

问题描述

考虑以下代码：

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

我得到以下订购class H：

H.mro() -> H, E, F, B, G, C, D, A, object

为什么在这种情况下是Bbefore ，因为直接继承自并且仅间接继承自？GHGB

标签： pythonmethod-resolution-order

解决方案

C3 的工作方式在此处有详细记录。但是我们可以针对您的具体示例进行处理，以了解您为什么会得到您所做的结果。

线性化算法并不难理解。它有两个递归部分。我将调用的公共接口mro（上面的文档使用L[x]而不是mro(x)，但我将坚持使用 Python-ish 语法）。另一部分是一个名为merge.

该mro功能非常容易理解。它[object]在基本情况下返回，即在object类型上调用它时，或者它首先返回一个带有其参数的列表，然后是merge调用返回的值，该值mro是在其参数的所有基数的 s 上调用的。这是 Python 中一个快速而肮脏的实现：

def mro(cls):
    if cls is object:
        return [object]
    return [cls] + merge([mro(base) for base in cls.__bases__])

合并有点复杂。它的参数是一个列表列表，每个列表都是mro基类的。如果只有一个列表，则结果merge非常简单（只是同一个列表）。那是单继承的情况。但是这种行为不需要任何特殊情况代码，它会从算法中出现。该算法表示扫描您传递的列表，以便找到第一个有效值以放入结果 mro。一个有效值只出现在它所在的参数列表的开头，永远不会出现在列表的更深处。一旦你有了一个有效的值，你就把它放在结果的前面，然后递归每个列表的其余部分（不包括你刚刚提取的值）。

这也是一个 Python 实现：

def merge(mros):
    if not any(mros): # all lists are empty
        return []  # base case
    for candidate, *_ in mros:
        if all(candidate not in tail for _, *tail in mros):
            return [candidate] + merge([tail if head is candidate else [head, *tail]
                                        for head, *tail in mros])
    else:
        raise TypeError("No legal mro")

创建列表参数列表的列表理解merge有点棘手。它只是删除了对candidate出现在列表开头的引用，并丢弃了之后空的所有列表（这样我们就可以知道何时停止递归）。

无论如何，让我们看看这些函数如何处理您的类层次结构，当您调用mro(H).

第一个调用是 to ，它运行函数代码mro(H)的一般情况。mro这会导致三个递归调用，以获取和的mros 。希望这些不会让您感到困惑，因为我真的不想深入研究它们（因为导致您所询问的奇怪的算法部分稍后会出现）。因此，在这些递归调用解决之后，我们调用结果。这作为我们的调用堆栈：EFGmromerge

mro(H)->
   return [H] + merge([[E, B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])

merge代码现在运行。它检查的第一个候选者是E，它是一个有效的候选者，因为E它不会出现在列表头部以外的任何地方。所以它删除E并递归。新的调用堆栈：

mro(H)->
   [H] + merge([[E, B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])
merge([[E, ...], [F, ...], [G, ...]]) ->
   [E] + merge([[B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])

在下一次运行中，它首先尝试B作为候选者，但这并不好，因为它在第二个列表中排名第二。所以它继续尝试F，这是有效的：

mro(H)->
   [H] + merge([[E, B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])
merge([[E, ...], [F, ...], [G, ...]]) ->
   [E] + merge([[B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])
merge([[B, ...], [F, ...], [G, ...]]) ->
   [F] + merge([[B, C, A, object], [B, D, A, object], [G, C, D, A, object]])

对于您的问题，下一个电话是有趣的电话。merge代码中要测试的第一个候选者是B，因为它是第一个列表的头部。这次证明是有效的，因为它也是第二个列表的头部（而不是上次的尾部），并且根本不在第三个列表中。所以它是在递归之前被删除的结果，而不是G（如你所料）。

mro(H)->
   [H] + merge([[E, B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])
merge([[E, ...], [F, ...], [G, ...]]) ->
   [E] + merge([[B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])
merge([[B, ...], [F, ...], [G, ...]]) ->
   [F] + merge([[B, C, A, object], [B, D, A, object], [G, C, D, A, object]])
merge([[B, ...], [B, ...], [G, ...]]) ->
   [B] + merge([[C, A, object], [D, A, object], [G, C, D, A, object]])

从这里开始，事情就变得非常简单了，因为第三个列表中的值最终会被一一删除（早期列表中的值也会同时删除）。我将只显示调用堆栈，而不是对每一个进行评论：

mro(H)->
   [H] + merge([[E, B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])
merge([[E, ...], [F, ...], [G, ...]]) ->
   [E] + merge([[B, C, A, object], [F, B, D, A, object], [G, C, D, A, object]])
merge([[B, ...], [F, ...], [G, ...]]) ->
   [F] + merge([[B, C, A, object], [B, D, A, object], [G, C, D, A, object]])
merge([[B, ...], [B, ...], [G, ...]]) ->
   [B] + merge([[C, A, object], [D, A, object], [G, C, D, A, object]])
merge([[C, ...], [D, ...], [G, ...]]) ->
   [G] + merge([[C, A, object], [D, A, object], [C, D, A, object]])
merge([[C, ...], [D, ...], [C, ...]]) ->
   [C] + merge([[A, object], [D, A, object], [D, A, object]])
merge([[A, ...], [D, ...], [D, ...]]) ->
   [D] + merge([[A, object], [A, object], [A, object]])
merge([[A, object], [A, object], [A, object]]) ->
   [A] + merge([[object], [object], [object]])
merge([[object], [object], [object]]) ->
   [object] + merge([])
merge([]) -> 
   []   # base case

推荐阅读