Python 内置属性 MRO 算法解析
什么是 MRO
MRO(Method Resolution Order): 方法解析顺序.
Python 语言包含了很多优秀的特性, 其中多重继承就是其中之一, 但是多重继承会引发很多问题, 比如二义性, Python 中一切皆引用, 这使得他不会像 C++ 一样使用虚基类处理基类对象重复的问题, 但是如果父类存在同名函数的时候还是会产生二义性, Python 中处理这种问题的方法就是 MRO.
对于 MRO 的历史问题这个帖子说的非常详细, 但是后面说到 C3 算法的时候说错了. 从评论中可以看出来.
python 内置属性 MRO http://python.jobbole.com/85685/ 请不要看这个地方.
请不要看这个地方
这文章有点瑕疵, 因为按照他的思路这个地方就不对了.
研究了一晚上才梳理了所有细节. 听我慢慢道来.
在箭头之前的你都可以看一下, 写的非常好. 等你看到这个的时候, 你需要了解什么是拓扑排序
拓扑排序
了解这一部分的可以跳到下面去.
重点: 一个图的拓扑排序是可以有多个的!!!!
经典实现算法:
kahn 算法
基于 DFS 的拓扑排序
很多情况下, 拓扑排序问题往往会出现在一些中等复杂程度的计算系统中. 这方面最典型的例子莫过于软件安装了, 现在大多数操作系统都至少会有一个自动安装软件组件的系统 (Ubuntu Linux 系统中的 apt-get,CentOS Linux 系统中的 RPM,Mac OS X 系统中的 brew 等), 这些系统会自动检测依赖关系中缺少的部分, 并下载安装它们, 对于这一类工作, 相关组件就必须按照一定的拓扑顺序来安装.
Kahn 算法:
摘一段维基百科上关于 Kahn 算法的伪码描述:
L← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
- while S is non-empty do
- remove a node n from S
- insert n into L
- foreach node m with an edge e from nto m do
- remove edge e from thegraph
- ifm has no other incoming edges then
- insert m into S
- if graph has edges then
- return error (graph has at least onecycle)
- else
- return L (a topologically sortedorder)
思想很简单, 首先用邻接表来构建一个图. 然后用一个临界表来记录每个顶点的入度, 再用一个表来加入入度为 0 的点. 最后一次输出.(什么是入度? a 入度为 0 代表没有点能指向 a, 为 1 就是又一个点能指向 a)
方法如下:
首先初始化一个表存放着这个图入度为 0 的点 S.
从这个表里面取数据 (如果这个表是栈, 就是先进后出的取, 如果是队列, 就是先进先取. 从这可以看出为什么拓扑排序为什么不唯一.), 将该顶点放入 List 中.
通过循环遍历由上面去出的顶点引出的所有边, 同时获取该边的另外一个顶点, 如果改顶点的入度在减去本条边之后为 0, 那么就把这个顶点放到 S 的集合中, 然后继续重复 2 的动作.
当集合为空之后, 检查图中是否还存在任何边, 如果存在的话, 说明图中存在环路. 不存在, 返回结果 List, 此 List 中的顺序就是拓扑排序的结果.
需要代码实现的盆友看这里:
拓扑排序代码实现 java
参看链接如下:
参看链接
我总觉得按照链接中楼主的思路, 红色的地方是有错误的. 谁能私聊我讨论讨论.
复杂度分析:
初始化入度为 0 的集合需要遍历整张图, 检查每个节点和每条边, 因此复杂度为 O(E+V);
然后对该集合进行操作, 又需要遍历整张图中的, 每条边, 复杂度也为 O(E+V);
因此 Kahn 算法的复杂度即为 O(E+V).
C3 算法
既然弄懂来拓扑排序, 那么我们来看看 C3 算法到底如何工作的.
官网解释链接, 英语还行的可以看看
快速查看, 看看这个对官网的翻译链接
箭头是核心, 懂这一块, 应该就没有问题来.
来源: http://www.jianshu.com/p/c1afc34257d7