c3 linearization详解
本帖最后由 wshuo 于 2022-4-7 12:41 编辑### MRO
MRO 全称方法解析顺序（Method Resolution Order），在多重继承和多继承存在的时候，寻找属性及方法的顺序。
### 深度优先(DFS)与广度优先(BFS)
python2 所用的 mro 就是深度优先的算法，但是深度优先针对菱形继承会有问题，如图：
DFS: A->B->D->C
BFS:A->B->C->D
如果使用深度优先的算法，C重载了D的一个方法，会导致搜索不到C的重载，只会用到D
那么针对这种菱形继承应该使用BFS。
---
然而BFS 同样也会具有问题，如图：
DFS: A->B->D->C->E
BFS: A->B->C->D->E
针对这种继承如果使用广度优先，C和D有同名方法，正常应该使用D的方法(D，B应为一个整体，B的优先级比C高)，但是如果广度优先就会使用到C的方法。
### C3 linearization 测试
为了解决以上问题 python3 使用的mro是 **c3 linearization** 算法，翻译就是 c3线性化算法，也就是本文重点介绍的内容。
可以简单看一下 python3 针对上述俩种继承的解析顺序：
```python
# 菱形继承
class D:
pass
class B(D):
pass
class C(D):
pass
class A(B,C):
pass
print(A.__mro__)
```
输出：
```
(<class '__main__.A'>, <class '__main__.B'>, <class '__main__.C'>, <class '__main__.D'>, <class 'object'>)
```
```python
class D:
pass
class E:
pass
class B(D):
pass
class C(E):
pass
class A(B,C):
pass
print(A.__mro__)
```
输出：
```
(<class '__main__.A'>, <class '__main__.B'>, <class '__main__.D'>, <class '__main__.C'>, <class '__main__.E'>, <class 'object'>)
```
可以看到，顺序是合理的，但其使用即不是 DFS也不是BFS。其调用算法就是 c3 算法。
### C3 linearization 算法原理
首先我们定义几个符号的意义：(因为后面会用到公式表达)
| 符号| 意义 |
| ----- | -------------------------------------------------------- |
| L | 针对一个类进行解析用L进行表示，例如L(A)表示对类A进行解析 |
| merge | 合并操作的一个函数（后面具体介绍） |
| C | 表示一个类名 |
| B | 表示是C的一个子类，如果多个子类用B1，B2....表示 |
| + | 元素列表顺序添加 |
| tail| 去除列表第一个元素，例如 tail() = |
下面是一个关键定义：
```
L(C) = C + merge(L(B1) + L(B2) + ...+ )
```
merge函数是如何合并的：
1. 首先选中merge 函数的第一个参数(也是一个列表)，按照公式里的描述就是L(B1)。
2. 取列表中第一个元素记为h，如果h没有出现其他 列表的`tail`中， 那么将其移到 merge函数前，提取出来，并且将这个元素在所有列表中移除，并重复 2。
3. 如果出现在其他列表中的 `tail` 中，寻找下一个列表。
4.merge 函数所有元素都被移除类创建成功，如果寻找不到下一个列表则创建失败。
看到这里可能有点懵，下面具体举一个例子：
```python
class X():
pass
class Y():
pass
class A(X, Y):
pass
class B(X, Y):
pass
class F(A, B):
pass
print(F.__mro__)
```
我们来解析 F的mro顺序，则首先记为 `L(F)`，根据
```
L(C) = C + merge(L(B1) + L(B2) + ...+ )
```
公式得到:
```
L(F) = F + merge(L(A)+L(B))
```
接下来计算L(A)，与L(B):
```
L(A) = A + merge(L(X),L(Y)) = A + merge(,) =
L(B) = B + merge(L(X),L(Y)) = B + merge(,) =
```
带入 `L(F) = L(F) + merge(L(A)+L(B))` 得到：
```python
L(F) = F + merge(,)
```
下面是关键merge逻辑理解了，首先根据 merge 的说明 1，选中得到 ``, 根据merge的说明2，选中第一个元素 A， 判断A 是否在 `tail(B,X,Y)` 中，即 A 是否在 `` 中，不在，将其提出来，得到：
```
L(F) = F + merge(,) = + merge(,)
```
接着重复 merge的2，判断 X 是否在`tail(B,X,Y)=` 中，结果是存在，那么寻找``的下一个列表，即``，判断B 是否存在 `tail()=` 中，不存在，提出B，得到：
```
L(F) = F + merge(,) = + merge(,) = + merge(,)
```
剩下逻辑一样，依次提出 X和Y:
```
L(F) = F + merge(,) = + merge(,) = + merge(,) =
```
可以将我上述**python**代码运行一下结果和我们手算的是一样的：
```
(<class '__main__.F'>, <class '__main__.A'>, <class '__main__.B'>, <class '__main__.X'>, <class '__main__.Y'>, <class 'object'>)
```
### 复杂的解析(练手逻辑)
```
L(K1) = K1 + merge(L(C), L(A), L(B))
= K1 + merge(, , )
= + merge(, , )
= + merge(, , )
= + merge(, , )
=
L(K2) =
L(K3) =
L(Z)= Z + merge(L(K1), L(K3), L(K2))
= Z + merge(,,)
= + merge(, , )
= + merge(, , )
= + merge(,, )
= + merge(, , )
= + merge(, ,)
= + merge(, , )
= + merge(, , )
= + merge(, , )
=
```
```python
class O:
pass
class C(O):
pass
class A(O):
pass
class B(O):
pass
class D(O):
pass
class E(O):
pass
class K1(C,A,B):
pass
class K3(A,D):
pass
class K2(B,D,E):
pass
class Z(K1,K3,K2):
pass
print(Z.__mro__)
```
其实我看到很多文章有这种写法：
```
L(K1) = K1 + merge(L(C), L(A), L(B),(C,A,B))
```
这个`(C,A,B)`写不写都可以，最后都是要删除的，很多国外网站文章习惯这么写，应该是便于理解。
### 手写一个C3 linearization 算法
理解了merge的原理，我想我可以简单实现一下这个算法，可能你已经想象到了针对 L 的函数需要用到递归实现，merge参数传递一个二维数组就可以。
```python
class O:
pass
class C(O):
pass
class A(O):
pass
class B(O):
pass
class D(O):
pass
class E(O):
pass
class K1(C,A,B):
pass
class K3(A,D):
pass
class K2(B,D,E):
pass
class Z(K1,K3,K2):
pass
import copy
# merge_list 为一个二维的数组
def merge(merge_list):
index = 0
res = []
while index < len(merge_list):
if "".join(["".join(i) for i in merge_list]) == "":
break
if merge_list == []:
index += 1
first = merge_list
t = copy.deepcopy(merge_list)
t.pop(index)
temp_all = "".join(["".join(i) for i in t])
if first not in temp_all:
for temp_list in merge_list:
if first in temp_list:
temp_list.remove(first)
res.append(first)
else:
index += 1
return res
def L(arg_class):
if arg_class.__bases__.__name__ == 'object':
return
res =
res += merge()
return res
print(Z.__mro__)
print(L(Z))
```
我也没好好优化这个算法，反正能跑通，另外无法测试 错误继承，因为错误继承在类的实现的时候就会报错，为了方便测试我自己算法是否正确(看看`__mro__`属性就可以了)，类的继承使用和python内置继承，没有自己写继承逻辑。
吐槽一下，52破解不支持markdown流程图，导致我还截图上传的 作为Python初学者 感觉不简单啊，楼主我的榜样。 大佬研究的东西好高深
页:
[1]