メモ化でフィボナッチ数列計算を高速に

メモ化（メモワイズ）というのは、計算結果をキャッシュしておいて次の計算の時に再利用するという仕組みです。Julia用のメモ化のためのパッケージ (Memoise.jl) が開発されていますが、簡単な実装でフィボナッチ数列の計算がどのくらい速くなるのか試してみました。

まずはナイーブなフィボナッチ数列の計算プログラムです。

function fib(n)
  if n <= 2
    return 1
  else
    return fib(n-2) + fib(n-1)
  end
end

これを実行すると、以下のようになりました。@timeを付けると実行にかかった時間を計測してくれます。Apple M1 Maxでの実行です。

@time fib(1)
  0.000000 seconds
1

@time fib(2)
  0.000001 seconds
1

@time fib(5)
  0.000004 seconds
5

@time fib(10)
  0.000001 seconds
55

@time fib(20)
  0.000027 seconds
6765

@time fib(50)
 47.893291 seconds
12586269025

次にメモ化を実装してみます。フィボナッチ数列の入力をkey、出力の値をvalueとして、ハッシュテーブルに登録すれば良さそうです。memoise_fibという辞書（ハッシュテーブル）を作り、n番目のフィボナッチ数列が登録されていればその値を返し、登録されていなければ計算して辞書に登録する、というアルゴリズムです。

前術のフィボナッチ数列のアルゴリズムが遅いのは、fib(n) = fib(n-1) + fib(n-2) において、fib(n-1) には fib(n-2) の計算が含まれているにもかかわらず fib(n-2) を再計算しているところにあります。メモ化してあれば再計算が必要なくなります。

memoise_fib = Dict{BigInt, BigInt}();

function fib(n)
  v = get(memoise_fib, n, nothing)
  if isnothing(v)
    if n <= 2
      memoise_fib[n] = 1
      return 1
    else
      v = fib(n-2) + fib(n-1)
      memoise_fib[n] = v
      return v
    end
  else
    return v
  end
end

実行結果は以下のようになりました。高速です。

@time fib(1)
  0.076642 seconds (110.55 k allocations: 6.992 MiB, 99.88% compilation time)
1

@time fib(2)
  0.000007 seconds (4 allocations: 80 bytes)
1

@time fib(5)
  0.014464 seconds (9.62 k allocations: 662.883 KiB, 99.26% compilation time)
5

@time fib(10)
  0.000010 seconds (20 allocations: 440 bytes)
55

@time fib(20)
  0.000017 seconds (43 allocations: 2.109 KiB)
6765

@time fib(50)
  0.000018 seconds (123 allocations: 7.406 KiB)
12586269025

最初の方法だと現実的な時間では計算できない1000番目のフィボナッチ数も、以下のようにあっという間に計算できます。いつもJuliaはすごいのですが、こればかりはメモ化の威力です。

@time fib(1000)
  0.000274 seconds (5.27 k allocations: 228.781 KiB)
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875