はじめに
Python で Memoize (Memoization / メモ化) する方法をお伝えします。
※「Memoize」は「Memoization」や「メモ化」ともいいます。
Memoize とは
Memoize とは、キャッシュを用いて関数呼び出しを高速化する手法のことです。関数呼び出し時の引数をキーとして戻り値をキャッシュし、同じ引数で呼び出された場合にキャッシュした値を返す (関数呼び出しを省略する) ことで高速化します。
Memoize の効果が高い場合
関数が以下の特徴を持つときは、Memoize することで大きな効果を期待できます。
- 関数が同じ引数で何度も呼び出される
- 関数呼び出し 1 回あたりのコストが高い (実行時間が長い)
例としてフィボナッチ数を求める再帰関数を定義します。引数 n の値が大きくなるほど、関数 fibonacci は同じ引数で何度も呼び出されます。こういう関数を Memoize することで、大幅に高速化することができます。
# 再帰でフィボナッチ数を求める関数は Memoize する効果が高い.
def fibonacci(n):
if n < 0:
raise ValueError
if n in (0, 1):
return n
return fibonacci(n - 1) + fibonacci(n - 2)
Memoize するデコレータ
functools のデコレータ
標準ライブラリの functools にも Memoize するための関数が存在します。lru_cache と cache です。cache は lru_cache(maxsize=None) と同じです。
次のように使います。
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(target):
cache = {}
def wrapper(*args, **kwargs):
key = args + tuple(kwargs.items())
if not hashable(key):
return target(*args, **kwargs)
if key not in cache:
cache[key] = target(*args, **kwargs)
return cache[key]
return wrapper
以下、使用例です。
@memoize
def fibonacci(n):
if n < 0:
raise ValueError
if n in (0, 1):
return n
return fibonacci(n - 1) + fibonacci(n - 2)
if __name__ == "__main__":
for n in range(32):
print(f"fibonacci({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 target(*args, **kwargs) # ← キャッシュすることを諦め, 関数呼び出しする.
if key not in cache:
cache[key] = target(*args, **kwargs)
return cache[key]