メソッドの検索順序

Python

Python2.3以降の新しいクラスは、メソッドの検索順序(MRO, Method Resolution Order)が「C3線形化」というアルゴリズムに変更されている。このアルゴリズムについて解説する。

まずは実例。

>>> class A(object): x = "a"
>>> class B(A): pass
>>> class C(A): x = "c"
>>> class D(object): x = "d"
>>> class E(B, C, D): pass
>>> e = E()
>>> e.x
'c'

クラスの検索順序が深さ優先探索ではないことがわかると思う。

C3線形化の特徴はメソッドを探す順番が

  • クラスXがYを継承しているなら必ずXがYより先にくる
  • クラスXがY, Zという順で継承しているならYは必ずZより先に来る
  • 他のクラスのメソッド探索順でXがYより先に来ているなら、他のクラスの探索順でも必ずXはYの前にある

という3つの条件を満たすことである。

かりにメソッド探索の順番が深さ優先探索だと、上のE.xはまずEの中で探して、次にBの中を探し、次にBの親クラスであるAの中を探す。そうすると実際にはCがAを継承しているにもかかわらずAが先に検索されてしまうためC.xでオーバーライドされているのが反映されない。これがPython2.2以前の挙動。

幅優先でない証拠は下記

>>> class A(object): x = "a"
>>> class B(A): pass
>>> class C(object): x = "c"
>>> class D(B, C): pass
>>> d = D()
>>> d.x
'a'

幅優先探索ならD→B→C→Aの順に検索されることになるが、それではBはAからxを継承しているはずなのにC.xの値が返ってしまう。Pythonは実際にはD→B→A→Cの順に探索している。

まずクラスがどういう順になっているかというリスト(CPL)を作るアルゴリズム。

  • [B, A, object]
  • [C, object]
  • [D, B, C]

これを並べるときに、まずobjectの部分がマージされて

  • [((B, A) | C), object]

こんな感じになる。ここで(B, A)とCのどっちを前にするか考えるわけだけど、[D, B, C]の中でBが先になっているから

  • [B, A, C, object]

こうなる。最後にこれと無矛盾なD, B, Cがマージされて

  • [D, B, A, C, object]

こうなる。

最初の例は

  • [B, A, object]
  • [C, A, object]
  • [D, object]
  • [E, B, C, D]

だった。これも

  • [((B, A) | (C, A) | D), object]

こうなって、BやCよりDがあとなので

  • [(B | C), A, D, object]

こうなって、BがCより前なので

  • [B, C, A, D, object]

こうなって最後に

  • [E, B, C, A, D, object]

こうなる。

で、いいのかな？ちがうかな。

クラスが定義されたときに順番が決まるべきか。
つまり、

  • [A, object]

がまず決まって、次にB(A)で

  • [B, A, object]

C(A)で

  • [C, A, object]

となって、最後にD(B, C)で

  • [D,

まで来たときに、どれを選ぶか、と言う話でD(B,C)だからBが選ばれ

  • [D, B

となり、次はAとCのどちらを選ぶかという話になって、CのCPLにAが含まれているからCが先に来て

  • [D, B, C, A, object]

ってなるんかな。

2番目の例だと

  • [A, object]
  • [B, A, object]
  • [C, A, object]
  • [D, object]
  • [E,

でE(B, C, D)だからBが選ばれ

  • [E, B,

Bの次のAとCとDだと、CのCPLがAを含んでいるので先に来て

  • [E, B, C,

Bの次のAとDだと、DのCPLはAを含んでいなくてBが含んでいるのでE(B, C, D)の順に従ってAが選ばれ

  • [E, B, C, A,

Aの次のobjectとDだとDのCPLがobjectを含んでいるのでDが先に来て

  • [E, B, C, A, D, object]

となるのか。

うん、こっちの方が実装として普通そうだ。

        • -

The Python 2.3 Method Resolution Order
http://www.python.org/download/releases/2.3/mro/index.html#the-c3-method-resolution-order

ここの説明がとてもわかりやすかった。