你真的理解Python中MRO算法吗?

500 查看

【前言】

MRO(Method Resolution Order):方法解析顺序
Python语言包含了很多优秀的特性,其中多重继承就是其中之一,但是多重继承会引发很多问题,比如二义性,Python中一切皆引用,这使得他不会像C++一样使用虚基类处理基类对象重复的问题,但是如果父类存在同名函数的时候还是会产生二义性,Python中处理这种问题的方法就是MRO。

【历史中的MRO】

如果不想了解历史,只想知道现在的MRO可以直接看最后的C3算法,不过C3所解决的问题都是历史遗留问题,了解问题,才能解决问题,建议先看历史中MRO的演化。
Python2.2以前的版本:经典类(classic class)时代
经典类是一种没有继承的类,实例类型都是type类型,如果经典类被作为父类,子类调用父类的构造函数时会出错。
这时MRO的方法为DFS(深度优先搜索(子节点顺序:从左到右))。

inspect.getmro(A)可以查看经典类的MRO顺序

MRO的DFS顺序如下图:

36071EB6-F4FF-46FA-99F2-F3A205FB7353

两种继承模式在DFS下的优缺点。
第一种,我称为正常继承模式,两个互不相关的类的多继承,这种情况DFS顺序正常,不会引起任何问题;

第二种,棱形继承模式,存在公共父类(D)的多继承(有种D字一族的感觉),这种情况下DFS必定经过公共父类(D),这时候想想,如果这个公共父类(D)有一些初始化属性或者方法,但是子类(C)又重写了这些属性或者方法,那么按照DFS顺序必定是会先找到D的属性或方法,那么C的属性或者方法将永远访问不到,导致C只能继承无法重写(override)。这也就是为什么新式类不使用DFS的原因,因为他们都有一个公共的祖先object。


Python2.2版本:新式类(new-style class)诞生
为了使类和内置类型更加统一,引入了新式类。新式类的每个类都继承于一个基类,可以是自定义类或者其它类,默认承于object。子类可以调用父类的构造函数。

这时有两种MRO的方法
1. 如果是经典类MRO为DFS(深度优先搜索(子节点顺序:从左到右))。
2. 如果是新式类MRO为BFS(广度优先搜索(子节点顺序:从左到右))。

MRO的BFS顺序如下图:

6C3FAA19-5C47-426D-9AB2-99789FAEBE6D

两种继承模式在BFS下的优缺点。
第一种,正常继承模式,看起来正常,不过实际上感觉很别扭,比如B明明继承了D的某个属性(假设为foo),C中也实现了这个属性foo,那么BFS明明先访问B然后再去访问C,但是为什么foo这个属性会是C?这种应该先从B和B的父类开始找的顺序,我们称之为单调性。

第二种,棱形继承模式,这种模式下面,BFS的查找顺序虽然解了DFS顺序下面的棱形问题,但是它也是违背了查找的单调性。

因为违背了单调性,所以BFS方法只在Python2.2中出现了,在其后版本中用C3算法取代了BFS。

Python2.3到Python2.7:经典类、新式类和平发展
因为之前的BFS存在较大的问题,所以从Python2.3开始新式类的MRO取而代之的是C3算法,我们可以知道C3算法肯定解决了单调性问题,和只能继承无法重写的问题。C3算法具体实现稍后讲解。

MRO的C3算法顺序如下图:看起简直是DFS和BFS的合体有木有。但是仅仅是看起来像而已。

7CA5DDFC-F5F4-4060-8B9F-21D123AB71E5

Python3到至今:新式类一统江湖
Python3开始就只存在新式类了,采用的MRO也依旧是C3算法。

【神奇的算法C3】

C3算法解决了单调性问题和只能继承无法重写问题,在很多技术文章包括官网中的C3算法,都只有那个merge list的公式法,想看的话网上很多,自己可以查。但是从公式很难理解到解决这个问题的本质。我经过一番思考后,我讲讲我所理解的C3算法的本质。如果错了,希望有人指出来。

假设继承关系如下(官网的例子):

首先假设继承关系是一张图(事实上也是),我们按类继承是的顺序(class A(B, C)括号里面的顺序B,C),子类指向父类,构一张图。
此处输入图片的描述

我们要解决两个问题:单调性问题和不能重写的问题。
很容易发现要解决单调性,只要保证从根(A)到叶(object),从左到右的访问顺序即可。
那么对于只能继承,不能重写的问题呢?先分析这个问题的本质原因,主要是因为先访问了子类的父类导致的。那么怎么解决只能先访问子类再访问父类的问题呢?如果熟悉图论的人应该能马上想到拓扑排序,这里引用一下百科的的定义:

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

因为拓扑排序肯定是根到叶(也不能说是叶了,因为已经不是树了),所以只要满足从左到右,得到的拓扑排序就是结果,关于拓扑排序算法,大学的数据结构有教,这里不做讲解,不懂的可以自行谷歌或者翻一下书,建议了解完算法再往下看。

那么模拟一下例子的拓扑排序:首先找入度为0的点,只有一个A,把A拿出来,把A相关的边剪掉,再找下一个入度为0的点,有两个点(B,C),取最左原则,拿B,这是排序是AB,然后剪B相关的边,这时候入度为0的点有E和C,取最左。这时候排序为ABE,接着剪E相关的边,这时只有一个点入度为0,那就是C,取C,顺序为ABEC。剪C的边得到两个入度为0的点(DF),取最左D,顺序为ABECD,然后剪D相关的边,那么下一个入度为0的就是F,然后是object。那么最后的排序就为ABECDFobject。