Python で Memoize する方法


# はじめに

Python で Memoize (Memoization / メモ化) する方法をお伝えします。

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

# Memoize とは

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

# Memoize の効果が高い場合

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

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

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

```python
# 再帰でフィボナッチ数を求める関数は 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)` と同じです。

 * lru_cache (Python 3.2 で追加) - [英語ドキュメント](https://docs.python.org/3/library/functools.html#functools.lru_cache), [日本語ドキュメント](https://docs.python.org/ja/3/library/functools.html#functools.lru_cache)
 * cache (Python 3.9 で追加) - [英語ドキュメント](https://docs.python.org/3/library/functools.html#functools.cache), [日本語ドキュメント](https://docs.python.org/ja/3/library/functools.html#functools.cache)

次のように使います。

```python
from functools import lru_cache

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

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

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

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

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

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

```python
# オブジェクトがハッシュ可能であるか判定する.
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
```

以下、使用例です。

```python
@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 のキーはハッシュ可能な値でなければなりません。

```python
# 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` の要素にハッシュ不可能な値が含まれる場合は、ハッシュしようとするとエラーになります。

```python
# 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` では、デコレートした関数の引数をキャッシュのキーとしています。

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

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

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

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

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

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

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

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

```python
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]
```