LRUキャッシュを使って再帰の効率化を試してみる

PythonのLRUキャッシュを使えばメモ化再帰が簡単かつ高速になるというのをどこかで見かけたので、試してみた。

fibonacci数列

この数列を計算してみる
$a_{n+2} = a_{n+1} + a_n$
$a_1 = a_2 = 1$

普通の再帰

# 0. normal
def fib0(i):
    if i == 1 or i == 2:
        return 1
    return fib0(i-1) + fib0(i-2)
n = int(input())
an = fib0(n)

これだと、再帰の過程で同じ計算を何度もしていて非効率(参考)
なので、同じ計算を繰り返さないように配列に入れておく(メモ化)

メモ化再帰

#1. memo
def fib1(i, memo):
    if memo[i] != -1:
        return memo[i]
    memo[i] = fib1(i-1, memo) + fib1(i-2, memo)
    return memo[i]
n = int(input())
memo = [-1] * (n+1)
memo[0] = 1
memo[1] = 1
an = fib1(n, memo)

こうすると、一回計算されたものがmemo配列に保存されているので、$O(N)$で計算が済む

LRU Cache

さらに、functoolsを用いてLRU Cacheを使うと更に効率化される。
関数の引数に対する計算結果を保存して、同じ引数が後で来たらその計算結果を再利用してくれる。書き方は簡単でノーマルの再帰的に@lru_cacheのデコレータをつけるだけ。コードもきれいにかけるので便利。

# 2. lrucache
from functools import lru_cache
@lru_cache(maxsize=None)
def fib2(i):
    if i == 0 or i == 1:
        return 1
    return fib2(i-1) + fib2(i-2)
n = int(input())
an = fib2(n)

配列メモ化 v.s LRU cache

• 縦軸 : 実行時間(ms)
• 横軸 : 項数

配列によるメモ化より、LRU cacheを使うほうがちょっとだけ早いみたい。便利そう