python多重继承新算法C3介绍

yipeiwu_com5年前Python基础

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]

相关文章

pygame库实现移动底座弹球小游戏

pygame库实现移动底座弹球小游戏

本文实例为大家分享了pygame实现移动底座弹球的具体代码,供大家参考,具体内容如下 输出结果:   实现代码: # -*- coding: utf-8 -*- #Py...

基于asyncio 异步协程框架实现收集B站直播弹幕

前言 虽然标题是全站,但目前只做了等级 top 100 直播间的全天弹幕收集。 弹幕收集系统基于之前的B 站直播弹幕姬 Python 版修改而来。具体协议分析可以看上一篇文章。 直...

python生成器,可迭代对象,迭代器区别和联系

python生成器,可迭代对象,迭代器区别和联系

生成器,可迭代对象,迭代器之间究竟是什么关系? 用一幅图来概括: 1.生成器 定义生成器 方式一: //区别于列表生成式 gen = [x*x for x in range(...

通过PYTHON来实现图像分割详解

程序思路: 此次程序主要是利用PIL(Python Image Libraty)这库,来进行图片的处理。 PIL是一个功能非常强大的python图像处理标准库,但由于PIL只支持pyth...

python 随机生成10位数密码的实现代码

随机生成10位数密码,字母和数字组合 import string >>> import random >>> pwd = "" >>&...