はじめに

Python で Memoize する方法をお伝えします。

Memoize とは

Memoize とは、キャッシュを用いて関数呼び出しを高速化する手法のことです。関数呼び出し時の引数をキーとして戻り値をキャッシュし、同じ引数で呼び出された場合にキャッシュの値を返す (関数呼び出しを省略する) ことで高速化します。

※「Memoize」は「Memoization」や「メモ化」ともいいます。

Memoize の効果が高い場合

関数が以下の特徴を持つときは、Memoize することで大きな効果を期待できます。

関数が同じ引数で何度も呼び出される
関数呼び出し 1 回あたりのコストが高い (実行時間が長い)

例としてフィボナッチ数を求める再帰関数を定義します。引数 n の値が大きくなるほど、関数 fibonacci は同じ引数で何度も呼び出されます。こういう関数を Memoize することで、大幅に高速化することができます。

# 再帰でフィボナッチ数を求める関数は Memoize する効果が高い.
def fibonacci(n):
    if n < 1:
        raise ValueError
    if n in (1, 2):
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

Memoize するデコレータ

functools.lru_cache

Python 3.2 から functools に lru_cache というでコレータがあります。

https://docs.python.org/3.7/library/functools.html#functools.lru_cache (英語ドキュメント)
https://docs.python.org/ja/3.6/library/functools.html#functools.lru_cache (日本語ドキュメント)

functools.lru_cache は次のように使います。

from functools import lru_cache

@lru_cache(maxsize = 64)
def f(x):
    return x

functools.lru_cache は関数引数がハッシュ可能ではない場合にエラーとなります。

# ハッシュ可能な値を渡した場合.
>>> f(1)
1

# ハッシュ可能ではない引数を渡すと TypeError が発生する.
>>> f([1, 2, 3])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

ハッシュ可能ではない値でもエラーにしない実装

ハッシュ可能ではない値でもエラーとしないようにするには、次のように実現することができます。

# オブジェクトがハッシュ可能であるか判定する.
def hashable(x):
    try:
        hash(x)
        return True
    except TypeError:
        return False

# 関数を Memoize するデコレータ.
def memoize(callable):
    cache = {}
    def wrapper(*args, **kwargs):
        key = args + tuple(kwargs.items())
        if not hashable(key):
            return callable(*args, **kwargs)
        if key not in cache:
            cache[key] = callable(*args, **kwargs)
        return cache[key]
    return wrapper

以下、使用例です。

@memoize
def fibonacci(n):
    if n < 1:
        raise ValueError
    if n in (1, 2):
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

if __name__ == "__main__":
    for i in range(32):
        n = i + 1
        print("fibonacci({}) = {}".format(n, fibonacci(n)))

実装上のポイント

実装上のポイントがいくつかあります。

Python の dict はハッシュ可能な値しかキーにできない
ハッシュ可能か判定するには組み込み関数の hash() を使う
関数引数から生成したキャッシュキーがハッシュ可能ではない場合は諦める

Python の dict はハッシュ可能な値しかキーにできない

Python では dict のキーはハッシュ可能な値でなければなりません。

# tuple はハッシュ可能なので dict のキーにできる.
>>> {(): "empty tuple"}
{(): 'empty tuple'}

# list はハッシュ可能ではないので dict のキーにするとエラーになる.
>>> {[]: "empty list"}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

ここで注意しなければならないのは、tuple は常にハッシュ可能ではないということです。tuple の要素にハッシュ不可能な値が含まれる場合は、ハッシュしようとするとエラーになります。

# tuple がハッシュ可能な値だけを含むなら, tuple 自体もハッシュ可能.
>>> hash((1, 2, 3))
2528502973977326415

# tuple がハッシュ可能ではない値を含むなら, tuple 自体はハッシュ可能ではない.
>>> hash((1, 2, [3]))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

先ほど定義したデコレータ memoize では、デコレートした関数の引数をキャッシュのキーとしています。

key = args + tuple(kwargs.items())

ただし、ここで生成した key はハッシュ可能であるとは限りません。tuple がハッシュ可能でない値を含むなら、tuple 自体もハッシュ可能ではないのでした。

ハッシュ可能か判定するには組み込み関数の hash() を使う

あるオブジェクトがハッシュ可能であるか判定するには、組み込み関数の hash() に渡してみる方法が手っ取り早いです。

# オブジェクトがハッシュ可能であるか判定する.
def hashable(x):
    try:
        hash(x)
        return True
    except TypeError:
        return False

別の方法として、渡された値の型を isinstance() で判定し、それが iterable だったら中身の値を再帰的に判定しても良いですが、実装の手間は格段に上がります。

関数引数から生成したキャッシュキーがハッシュ可能ではない場合は諦める

生成したキャッシュキーがハッシュ可能ではない場合は、キャッシュすることを諦めます。

key = args + tuple(kwargs.items())
if not hashable(key):
    return callable(*args, **kwargs) # ← 諦める
if key not in cache:
    cache[key] = callable(*args, **kwargs)
return cache[key]