【Python競プロ用メモ】LRUキャッシュはプログラムでのメモ化より早い

#１．一言で言うと
デコレータ@lru_cacheを使ったメモ化は、プログラムを使ったメモ化よりも早かった。

#２．フィボナッチ数列の和
フィボナッチ数列の和を、以下の３通りの方法で再帰的に計算し、再帰関数が呼び出された回数と処理時間を記録する。(環境はGoogle Colaboratory。)
（１）普通の再帰
（２）メモ化再帰
（３）LRUキャッシュ　@lru_cache

#３．普通の再帰
まずは、普通の再帰関数でフィボナッチ数列の和を求め、計測してみよう。

%%time
fib_cnt=0
def fib(n):
    global fib_cnt
    fib_cnt+=1
    if n<=1:
        return n
    return fib(n-1)+fib(n-2)
fib1=fib(35)
print('fib1=',fib1)
print('fib1_cnt=',fib_cnt)

実行結果は以下の通り。まあ、時間が掛かるよね。

fib1= 9227465
fib1_cnt= 29860703
CPU times: user 4.93 s, sys: 5 ms, total: 4.94 s
Wall time: 4.94 s

#４．メモ化再帰
次に、メモ化再帰でフィボナッチ数列の和を求め、計測してみよう。

%%time
fib2_cnt=0
def fib2(n):
    memo=[0]*(n+1)
    def fib3(n):
        global fib2_cnt
        fib2_cnt+=1
        if n<=1:
            return n
        if memo[n]!=0:
            return memo[n]
        memo[n]=fib3(n-1)+fib3(n-2)
        return memo[n]
    return fib3(n)
fib2=fib2(35)
print('fib2=',fib2)
print('fib2_cnt=',fib2_cnt)

実行結果は以下の通り。当然、早くなる。

fib2= 9227465
fib2_cnt= 69
CPU times: user 0 ns, sys: 1.69 ms, total: 1.69 ms
Wall time: 2.74 ms

気になるのは、呼び出される回数。フィボナッチ数列なので、前２数の和になるからか、35までのフィボナッチ数列の和の場合、約２倍の69回、呼び出されている。

#５．LRUキャッシュ　@lru_cache

最後に、LRUキャッシュ　@lru_cache　を使ったメモ化でやってみよう。LRUはLeast Recently Usedの略。最も最近、使った、ということだ。

%%time
from functools import lru_cache
fib4_cnt=0
@lru_cache(maxsize=None)
def fib4(n):
    global fib4_cnt
    fib4_cnt+=1
    if n<=1:
        return n
    return fib4(n-1)+fib4(n-2)
fib4=fib4(35)
print('fib4=',fib4)
print('fib4_cnt=',fib4_cnt)

この場合、呼び出される回数は、0から35までの36回。先ほどのプログラムでの再帰より呼び出される回数が少ない。

fib4= 9227465
fib4_cnt= 36
CPU times: user 1.74 ms, sys: 4 µs, total: 1.75 ms
Wall time: 1.61 ms

#６．まとめ
プログラムの構造上、今回の例では、プログラムでのメモ化再帰よりLRUキャッシュ　@lru_cache　の方が早い。プログラムを上手く書けば良いのかもしれないが、LRUキャッシュに無駄がないことが分かった。