9
Help us understand the problem. What are the problem?

More than 3 years have passed since last update.

posted at

updated at

Python で Memoize する方法

はじめに

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 というでコレータがあります。

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]
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
9
Help us understand the problem. What are the problem?