サブロウ丸

Sabrou-mal サブロウ丸

主にプログラミングと数学

Python functoolsのlru_cache

lru_cache

lru_cacheは関数の引数と返り値を保存する。

from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

公式の例。再帰的にフィボナッチ数を計算していますが、そのまま実行すると呆れるほど遅いです。
実際、この関数にnを渡すと約 2^{n} 回ほどこの関数が呼び出されることなりますが、関数の引数としてそのほとんどが、過去渡されたことのある引数が繰り返し渡されることになります。
@lru_cacheを関数の前につければ、引数nに対する返り値を保存します。つまり同じ引数が2回以上渡されるときは、2回目以降は実際に関数の中身を計算することはありません。

上記の例だと、これにより関数が呼び出される回数が約 2n回に減少するのです。

maxsizeに保存する回数を指定でき、Noneを渡すとデフォルトの128がmaxsizeに入ります。

from functools import lru_cache
@lru_cache(maxsize=None)
def fact(n):
    if n <= 1: 
                return 1
    return power(n-1)*n

factorialを計算する関数。ぶっちゃけ@lru_cacheを使うほどの計算量ではありませんが、いい例が思いつかなくて。
いい例を知っている、思いついた方がいれば教えてください。