面向对象-mro

一、mro概述

• 概念

  方法解析顺序，是python中用于处理二义性问题的算法

• 二义性

  问题一：有两个基类A类和B类，A和B中都定义了f()的方法，C继承了A和B，那么调用C的f()方法时会出现不确定性

  问题二：有一个基类A，定义了方法f()，B类和C类都继承自A类，D类继承了B和C类，此时出现一个问题，D类不知道继承B的F()还是C的F()

• C++解决二义性

  问题一：通过同名覆盖的方法解决

  问题二：通过虚继承来解决

• python解决二义性

  通过C3算法避免二义性的情况

• 经历过程

  a、python2.2以前的版本(经典类时代)

  b、python2.2版本(新式类诞生)

  c、python2.3到python2.7(经典类、新式类和平发展)

  d、python3至今(新式类一统江山)

• 示例代码

  class A(object):
      def f(self):
          pass
  class B(A):
      pass
  class C(A):
      pass
  class D(B, C):
      pass
  

二、python2.2以前

经典类时代

• 经典类

  特性：经典类是一种没有继承的类，对象都是type类型，如果经典类被作为父类，子类调用父类的构造函数时会出错

  class A:
      pass
  class B(A):
      pass
  

• mro的算法为深度优先算法(DFS)

  a、把根阶段压入栈结构中
  b、每次从栈中弹出一个元素，搜索所有它下一级元素，把这些元素压入栈中。并把这个元素记为它下一个元素的前驱
  c、找到所有的元素时程序结束
  d、如果遍历整个树还没有找到，程序结束

• 两种继承模式（正常继承模式、菱形继承模式）

  # 正常继承模式
  import inspect
  class D:
      pass
  class E:
      pass
  class B(D):
      pass
  class C(E):
      pass
  class A(B, C):
      pass
  print(inspect.getmro(A))
  # A B D C E
  

  # 菱形继承模式
  import inspect
  class D:
      pass
  class B(D):
      pass
  class C(D):
      pass
  class A(B, C):
      pass
  print(inspect.getmro(A))
  # A B D C
  

• MRO的DFS顺序

  

• 两种继承模式在DFS下的优缺点

  第一种：称为正常继承模式，两个互不相关的类的多继承，这种情况DFS顺序正常，不会引起任何问题

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

三、python2.2

新式类诞生

• 新式类

  特性：为了使类和内置的类型更加统一，引入新式类。新式类的每个类都继承于一个基类，可以是自定义的类或者其他类，默认是object，子类可以调用父类的构造函数

• 两种MRO算法

  • 如果是经典类使用DFS

  • 如果是新式类使用BSF(广度优先算法)

    a、把根阶段放到队列队尾

    b、每次从队列的头部取一个元素，搜索所有它下一级元素，把这些元素放到队列的末尾。并把这个元素记为它下一个元素的前驱

    c、找到所有的元素时程序结束

    d、如果遍历整个树还没有找到，程序结束

• 两种继承模式（正常继承模式、菱形继承模式）

  # 正常继承模式
  class D(object):
      pass
  class E:
      pass
  class B(D):
      pass
  class C(E):
      pass
  class A(B, C):
      pass
  print(A.__mro__)
  # A B C D E
  

  # 菱形继承模式
  class D(objcet):
      pass
  class B(D):
      pass
  class C(D):
      pass
  class A(B, C):
      pass
  print(A.__mro__)
  # A B C D
  

• MRO的BFS顺序

  

• 两种继承模式在BFS下的优缺点

  第一种：正常继承模式，看起来正常，但实际上感觉别捏，比如B继承D的f()函数，恰巧C中也实现了f()函数，那么BFS顺序先访问B在去访问C，f()函数会选择C的，这种应该先从B和B的父类开始找才是正确的顺序，称为单调性

  第二种：菱形集成模式，在BFS模式下解决了DFS查找顺序的问题，但是它也违背了单调性

四、python2.3到python2.7

经典类与新式类和平发展

在之前的BFS算法存在很大的问题，从python2.3开始新式类的MRO算法使用C3算法，C3算法解决了单调性问题和只能继承不能重写的问题

五、python3时代

新式类一统江山

• C3算法

  C3算法解决了单调性问题和只能继承无法重写问题

• 两种继承模式（正常继承模式、菱形继承模式）

  # 正常继承模式
  class D(object):
      pass
  class E:
      pass
  class B(D):
      pass
  class C(E):
      pass
  class A(B, C):
      pass
  print(A.__mro__)
  

  # 菱形继承模式
  class D(objcet):
      pass
  class B(D):
      pass
  class C(D):
      pass
  class A(B, C):
      pass
  print(A.__mro__)
  

• MRO的C3顺序

  

• 拓扑排序

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

• 模拟拓扑排序

  class D(object):
      pass
  class E(object):
      pass
  class F(object):
      pass
  class B(E, D):
      pass
  class C(D, F):
      pass
  class A(B, C):
      pass
  print(A.__mro__)
  # A B E C D F object
  

首先找到入读点为0的点，只有一个A，把A拿出来，把A相关的边裁剪掉，再找入读点为0的点，有两个(B、C)。根据最左侧原则，拿B，此时的顺序AB，把B相关的边裁剪掉。此时入读点为0的点有E和C，取最左侧是E，此时的顺序为ABE。裁剪掉E的相关边，此时只有一个入读点为0的点为C，取C，此时的顺序是ABEC。裁剪掉C的相关边，此时入读点为0的点有D和F，取左侧的D点，此时的顺序为ABECD，裁剪掉D的相关边，此时只有F的入读点为0，取F，此时的顺序ABECDF，裁剪掉F的相关边，此时只有object入读点为0，取object，此时顺序为ABECDFobject