python多重继承新算法C3介绍
mro即 method resolution order (方法解释顺序)，主要用于在多继承时判断属性的路径(来自于哪个类)。
在python2.2版本中，算法基本思想是根据每个祖先类的继承结构，编译出一张列表，包括搜索到的类，按策略删除重复的。但是，在维护单调性方面失败过（顺序保存），所以从2.3版本，采用了新算法c3。
为什么采用c3算法
c3算法最早被提出是用于lisp的，应用在python中是为了解决原来基于深度优先搜索算法不满足本地优先级，和单调性的问题。
本地优先级：指声明时父类的顺序，比如c(a,b)，如果访问c类对象属性时，应该根据声明顺序，优先查找a类，然后再查找b类。
单调性：如果在c的解析顺序中，a排在b的前面，那么在c的所有子类里，也必须满足这个顺序。
c3算法
判断mro要先确定一个线性序列，然后查找路径由由序列中类的顺序决定。所以c3算法就是生成一个线性序列。
如果继承至一个基类:
class b(a)
这时b的mro序列为[b,a]
如果继承至多个基类
class b(a1,a2,a3 ...)
这时b的mro序列 mro(b) = [b] + merge(mro(a1), mro(a2), mro(a3) ..., [a1,a2,a3])
merge操作就是c3算法的核心。
遍历执行merge操作的序列，如果一个序列的第一个元素，是其他序列中的第一个元素，或不在其他序列出现，则从所有执行merge操作序列中删除这个元素，合并到当前的mro中。
merge操作后的序列，继续执行merge操作，直到merge操作的序列为空。
如果merge操作的序列无法为空，则说明不合法。
例子：
class a(o):pass
class b(o):pass
class c(o):pass
class e(a,b):pass
class f(b,c):pass
class g(e,f):pass
a、b、c都继承至一个基类，所以mro序列依次为[a,o]、[b,o]、[c,o]
mro(e) = [e] + merge(mro(a), mro(b), [a,b])
= [e] + merge([a,o], [b,o], [a,b])
执行merge操作的序列为[a,o]、[b,o]、[a,b]
a是序列[a,o]中的第一个元素，在序列[b,o]中不出现，在序列[a,b]中也是第一个元素，所以从执行merge操作的序列([a,o]、[b,o]、[a,b])中删除a，合并到当前mro，[e]中。
mro(e) = [e,a] + merge([o], [b,o], [b])
再执行merge操作，o是序列[o]中的第一个元素，但o在序列[b,o]中出现并且不是其中第一个元素。继续查看[b,o]的第一个元素b，b满足条件，所以从执行merge操作的序列中删除b，合并到[e, a]中。
mro(e) = [e,a,b] + merge([o], [o])
= [e,a,b,o]
实现c3算法的代码
#-*- encoding:gbk -*-#
def mro_c3(*cls):
if len(cls)==1:
if not cls[0].__bases__:
return cls
else:
return cls+ mro_c3(*cls[0].__bases__)
else:
seqs = [list(mro_c3(c)) for c in cls ] +[list(cls)]
res = []
while true:
non_empty = list(filter(none, seqs))
if not non_empty:
return tuple(res)
for seq in non_empty:
candidate = seq[0]
not_head = [s for s in non_empty if candidate in s[1:]]
if not_head:
candidate = none
else:
break
if not candidate:
raise typeerror("inconsistent hierarchy, no c3 mro is possible")
res.append(candidate)
for seq in non_empty:
if seq[0] == candidate:
del seq[0]