ベンチマーク15 functools.total_ordering

functools.total_ordering を使う場合と使わない場合の動作速度について比較します。
functools.total_ordering を使う場合は、クラスは __eq__() と __lt__() のみ実装し、total_ordering で修飾されています。使わない場合は、クラスは残りの __ne__()、__le__()、__gt__()、__ge__()も実装されています。

==、!=、<、<=、>、>= の６演算子全てを呼んだの速度と、== と < だけを呼んだ場合の速度の、二通りについて比較を行います。

６演算子全てを呼ぶベンチマークのソースコードです。

rom functools import total_ordering
from benchmarker import Benchmarker

with Benchmarker(1000000, width=20, cycle=3, extra=1) as bench:
    @bench("total_ordering")
    def _(bm):
        # クラス定義
        @total_ordering  # デコレータ
        class Stored(object):  # __lt__() と __eq__() のみ定義
            def __init__(self, value):
                self.value = value

            def __lt__(self, rhs):
                return self.value < rhs.value

            def __eq__(self, rhs):
                return self.value == rhs.value

        lhs = Stored(1)
        rhs = Stored(2)
        for _ in bm:
            # ６演算子全てを呼び出し
            lhs == rhs
            lhs != rhs
            lhs < rhs
            lhs <= rhs
            lhs > rhs
            lhs >= rhs

    @bench("normal")
    def _(bm):
        # クラス定義
        class Stored(object):  # ６演算子全てを定義
            def __init__(self, value):
                self.value = value

            def __lt__(self, rhs):
                return self.value < rhs.value

            def __le__(self, rhs):
                return self.value <= rhs.value

            def __gt__(self, rhs):
                return self.value > rhs.value

            def __ge__(self, rhs):
                return self.value >= rhs.value

            def __eq__(self, rhs):
                return self.value == rhs.value

            def __ne__(self, rhs):
                return self.value != rhs.value

        lhs = Stored(1)
        rhs = Stored(2)
        for _ in bm:
            # ６演算子全てを呼び出し
            lhs == rhs
            lhs != rhs
            lhs < rhs
            lhs <= rhs
            lhs > rhs
            lhs >= rhs

測定結果です。

## benchmarker:         release 4.0.1 (for python)
## python version:      3.7.3
## python compiler:     Clang 6.0 (clang-600.0.57)
## python platform:     Darwin-18.7.0-x86_64-i386-64bit
...

## Ranking                real
normal                  1.1379  (100.0) ********************
total_ordering          1.7093  ( 66.6) *************

total_ordering は使わず、６つの演算子を自力で定義した方が、動作速度は速いです。
公式ドキュメントに書いてある通りの結果となりました。

続いて、total_ordering を使っているクラスでも定義されている、== と < だけを呼び出した場合の動作速度を比較します。

rom functools import total_ordering
from benchmarker import Benchmarker

with Benchmarker(1000000, width=20, cycle=3, extra=1) as bench:
    @bench("total_ordering")
    def _(bm):
        # クラス定義
        @total_ordering  # デコレータ
        class Stored(object):  # __lt__() と __eq__() のみ定義
            def __init__(self, value):
                self.value = value

            def __lt__(self, rhs):
                return self.value < rhs.value

            def __eq__(self, rhs):
                return self.value == rhs.value

        lhs = Stored(1)
        rhs = Stored(2)
        for _ in bm:
            # == と < だけ呼び出し
            lhs == rhs
            lhs < rhs

    @bench("normal")
    def _(bm):
        # クラス定義
        class Stored(object):  # ６演算子全てを定義
            def __init__(self, value):
                self.value = value

            def __lt__(self, rhs):
                return self.value < rhs.value

            def __le__(self, rhs):
                return self.value <= rhs.value

            def __gt__(self, rhs):
                return self.value > rhs.value

            def __ge__(self, rhs):
                return self.value >= rhs.value

            def __eq__(self, rhs):
                return self.value == rhs.value

            def __ne__(self, rhs):
                return self.value != rhs.value

        lhs = Stored(1)
        rhs = Stored(2)
        for _ in bm:
            # == と < だけ呼び出し
            lhs == rhs
            lhs < rhs

測定結果です。

## benchmarker:         release 4.0.1 (for python)
## python version:      3.7.3
## python compiler:     Clang 6.0 (clang-600.0.57)
## python platform:     Darwin-18.7.0-x86_64-i386-64bit
...

## Matrix                 real    [01]    [02]
[01] total_ordering     0.4125   100.0   100.3
[02] normal             0.4136    99.7   100.0

結果、動作速度は同じでした。
total_ordering が動作速度的に不利になるのは、未定義の演算子の結果を他の演算子から推測する処理部分にあるようです。

演算子の話⑤ functools.total_ordering

前回、__lt__() や __eq__() が定義されていても <= や >= はフォールバックしてくれない、という話をしました。
少し気の利かない仕様のような気がします。
これをフォローしてくれるのが functools の total_ordering です。

total_ordering はデコレータで、__lt__()、__le__()、__gt__()、__ge__() の４つの不等式系関数のうち最低１つと __eq__() を持っているクラスを修飾し、全６つの不等号・等号演算子に対応するようになります。

@total_ordering  # デコレータ
class Stored(object):
    def __init__(self, value):
        self.value = value

    def __lt__(self, rhs):
        return self.value < rhs.value

    def __eq__(self, rhs):
        return self.value == rhs.value

# 全６つの不等号・等号に対応
>>> Stored(1) < Stored(2)
True

>>> Stored(1) <= Stored(2)
True

>>> Stored(1) > Stored(2)
False

>>> Stored(1) >= Stored(2)
False

>>> Stored(1) == Stored(2)
False

>>> Stored(1) != Stored(2)
True

__le__() や __ge__() が定義されていなくても、<= や >= が呼ばれています。

と、一見便利そうな total_ordering ですが、実際にはあまり使う機会がありません。
第一の理由は、わざわざ total_ordering で修飾するのが煩わしい、ためです。__lt__() を定義した時点で < とそのフォールバックの > に対応でき、さらに __eq__() を定義することで == とそのフォールバックの != に対応できます。つまり、total_ordering の前提条件の時点で６つの不等号・等号のうち、４つはカバーできることになります。なので、total_ordering を使うよりも、あと１つ __le__() あたりを定義してした方が手っ取り早い、というわけです。
もう一つの理由は、total_ordering を使うと動作が遅くなる、ためです。不等式は数学的クラスでよく使われますが、数学的クラスでは動作速度が重要となります。そのような使用目的では、total_ordering を使うよりも、愚直に全６つの不等式・等式系関数を定義した方が、動作は速くなります。

演算子の話④ 不等号の実処理をもう少し

前回、前々回と、< 演算子と == 演算子の実処理を見てきました。
今回は、不等号の実処理について、２つのケースを見てみたいと思います。

[ケース１]
以下のような、__lt__() と __eq__() が定義されたクラスを考えます。

class Stored(object):
    def __init__(self, value):
        self.value = value

    def __lt__(self, rhs):  # <
        if isinstance(rhs, Stored):
            return self.value < rhs.value
        return NotImplemented

    def __eq__(self, rhs):  # ==
        if isinstance(rhs, Stored):
            return self.value == rhs.value
        return NotImplemented

このクラスは < と == に対応しているわけですから、あわよくば < と == の OR を取って、<= 演算子が反応するかとも思いますが、、、

>>> Stored(1) <= Stored(1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<=' not supported between instances of 'Stored' and 'Stored'

< と == を元に <= を推測する機能はありません。
前回見たように、== 演算子は is 演算子を使う動作となっているため、あくまで大小比較をする <= 演算子とは別次元という考え方なのかもしれません。


[ケース２]
以下のような __ge__() だけが定義されたクラスを考えます。

class Stored(object):
    def __init__(self, value):
        self.value = value

    def __ge__(self, rhs):  # >=
        if isinstance(rhs, Stored):
            return self.value >= rhs.value
        return NotImplemented

>= の否定が < になるはずなので、>= に対応するこのクラスに < 演算子が反応しても良いかと思いますが、、、

>>> Stored(1) < Stored(1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'Stored' and 'Stored'

>= を元に < を推測する機能はありません。
ケース１と合わせて見ると、他の演算子から別の演算子の結果を推測することはあまり行われないようです。!= 演算子が == 演算子を使っていることが特殊ルールである見なすのが良さそうですね。

演算子の話③ == 演算子 が行うこと

前回、< 演算子の実処理を見てみました。今回は == 演算子の実処理を見てみます。

== 演算子の実処理は以下のようなものです。

def impl_eq(lhs, rhs):
    # first try with (lhs == rhs)
    ret = lhs.__eq__(rhs)
    if ret != NotImplemented:
        return ret

    # second try with (rhs == lhs)
    ret = rhs.__eq__(lhs)
    if ret != NotImplemented:
        return ret

    # finally use 'is'
    raise lhs is rhs

最初に、最も素直な呼び出しである lhs.__eq__(rhs) を試します。
最初の呼び出しが NotImplemented を返すと、フォールバックとして、形は異なるが同じ意味の呼び出しであるはずの rhs.__eq__(lhs) を試します。
どちらも NotImplemented であれば、最終手段として左辺値と右辺値を is 演算子で比較した結果を返します。
== 演算子の実処理では直接例外が投げられない点が、< 演算子の実処理と異なる点です。

フォールバックが機能する例を示します。
以下のような、自身と同じ型 又は int型との __eq__() だけを備えたクラスを考えます。

class Stored(object):
    def __init__(self, value):
        self.value = value

    def __eq__(self, rhs):  # ==
        if isinstance(rhs, Stored):
            print('Stored == Stored')
            return self.value == rhs.value
        if isinstance(rhs, int):
            print('Stored == int')
            return self.value == rhs
        return NotImplemented

# 素直に Stored.__eq__(Stored) が呼ばれる
>>> Stored(1) == Stored(1)
Stored == Stored
True

# 素直に Stored.__eq__(int) が呼ばれる
>>> Stored(1) == 1
Stored == int
True

# int.__eq__(Stored) が定義されていないので、
# 代わりに Stored.__eq__(int) が呼ばれる
>>> 1 == Stored(1)
Stored == int
True

int.__eq__(Stored) は定義されていませんが、フォールバックにより、1 == Stored(1) の結果を得ることができました。



ちなみに、!= 演算子の実処理は以下のようなものです。

def impl_eq(lhs, rhs):
    # first try with (lhs != rhs)
    ret = lhs.__ne__(rhs)
    if ret != NotImplemented:
        return ret

    # second try with (rhs != lhs)
    ret = rhs.__ne__(lhs)
    if ret != NotImplemented:
        return ret

    # finally use == operation
    return not rhs == lhs

!= 演算子が定義されていなかった場合のフォールバックとして、== 演算子を使います。
== 演算子の実処理では != 演算子を使っていないのに、その逆は成り立っているというのはやや意外な気もします。

また、仮に __eq__() だけ定義されたクラスがあったとして、そのクラスは自動生成された __ne__() を持つことになります。自動生成された __ne__() は、__eq__() の戻り値を反転させたものを返します。

演算子の話② < 演算子 が行うこと

前回、dict.__lt__() はビルトイン定数 NotImplemented を返すという話をしました。これがどのような意味があるのか、< 演算子の実処理を見ると明らかになります。

< 演算子の実処理は以下のようなものです。

def impl_lt(lhs, rhs):
    # first try with (lhs < rhs)
    ret = lhs.__lt__(rhs)
    if ret != NotImplemented:
        return ret

    # second try with (rhs > lhs)
    ret = rhs.__gt__(lhs)
    if ret != NotImplemented:
        return ret

    # give up operator <
    raise TypeError

最初に、最も素直な呼び出しである lhs.__lt__(rhs) を試します。
最初の呼び出しが NotImplemented を返すと、フォールバックとして、形は異なるが同じ意味であるはずの rhs.__gt__(lhs) を試します。
どちらも NotImplemented であれば、例外を投げて終了します。


フォールバックが機能する例を示します。
以下のような、自身と同じ型との __gt__() だけを備えたクラスを考えます。

class Stored(object):
    def __init__(self, value):
        self.value = value

    def __gt__(self, rhs):  # >
        if isinstance(rhs, Stored):
            print('Stored > Stored')
            return self.value > rhs.value
        return NotImplemented

# 素直に Stored.__gt__(Stored) が呼ばれる
>>> Stored(2) > Stored(1)
Stored > Stored
True

# Stored.__lt__(Stored) が定義されていないので、
# 代わりに Stored.__gt__(Stored) が呼ばれる
>>> Stored(1) < Stored(2)
Stored > Stored
True

Storedクラスは __gt__() しか持っていなくとも、< 演算子で結果を得ることができました。これがフォールバックが働いた例となります。


フォールバックが特に役立つのは、分数クラスのように int や float と比較可能なクラスを自作した場合です。
int.__lt__(Fraction) は実装できませんが、Fraction側で Fraction.__lt__(int) などを実装しておけば、フォールバックが働くことで、1 < Fraction(1, 2) のような演算子を呼び出し可能となります。

演算子の話① NotImplemented とは？

Python のあまり有名でないと思われるビルトイン定数に NotImplemented があります。
これは演算子系の関数を呼び出した時に「戻り値」として使用されます。


簡単に NotImplemented を見る方法として、dict の __lt__() があります。

>>> ret = dict().__lt__(dict())
>>> ret
NotImplemented
>>> type(ret)
<class 'NotImplementedType'>

こちらで述べたように、dict は < 演算子に対応していません。対応していないのですが、dict.__lt__() という関数自体は存在しています。< 演算子から dict.__lt__() が呼び出され、戻り値としてビルトイン定数 NotImplemented（型は NotImplementedType）を返しているということになります。
では、ビルトイン定数 NotImplemented を返すことで、一体どのようなメリットがあるのでしょうか？　次回以降見ていきます。

コンテナと < 演算子

Python のコンテナに対して < 演算子を使った場合の結果をまとめてみます。

コンテナに < 演算子を使った結果として想像がつきやすいのが、いわゆる「辞書順」でしょう。
最も典型的な str に対する < 演算子の結果は以下のようになります。

>>> 'cnv' < 'conv' < 'convert'
True

関数として実装すると、以下のようになるでしょうか。

def lt(lhs, rhs):
    for i, j in zip(lhs, rhs):
        if i < j:
            return True
        elif j < i:
            return False
    return len(lhs) < len(rhs)

この辞書順は、str 以外にも list、tuple、bytes に適用されます。

# listも辞書順
>>> [1, 2] < [1, 2, 3] < [1, 3, 2]
True

続いて、set に対する < 演算子の結果を見てみましょう。

>>> {1, 2} < {1, 2, 3}
True
>>> {1, 2} < {1, 3, 4}
False
>>> {1, 2} < {1, 2}
False

ここで < 演算子は、数学の真部分集合（記号だと⊂）を表しています。
set には順番という概念がないので、< とは異なる記号の意味となるわけですね。
（ちなみに、<= 演算子は部分集合（記号だと∈）を表します。）

関数として実装すると、以下のようになるでしょうか。

def lt(lhs, rhs):
    return (len(lhs) != len(rhs)) and all(i in rhs for i in lhs)

さらに、dict に対する < 演算子の結果を見てみましょう。

>>> {1: 1} < {1: 1}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'dict' and 'dict'

TypeError となりました。dict はそもそも < 演算子に対応していないということになります。
言われてみれば、dict に < 演算子を適用したとして、結果が想像できませんよね。

同じように range も < 演算子に対応していません。

>>> range(5) < range(5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'range' and 'range'

一口に < 演算子と言っても、コンテナの種類によって演算結果は様々です。
< 演算子はデフォルトでのソートに直結しますので、この結果は頭に入れておきたいですね。