フィボナッチ数列の処理速度改善。

この記事はなに

Miniscriptっていう言語の動作テストでベンチマーク処理をベタ書きしたらあまりに出力が遅く、
改善案ないかな？って調べたらあったのでメモるもの。

あとMiniscriptの情報をまとめようと思って少しずつ書いてみるもの。

ベタ実装

単にフィボナッチ数列を書くだけなら早い。
ただ、数列50くらいだとスクリプト言語では計算結果が長時間帰ってこない。

この遅さはヤバい。

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

print fib(50)

動的計画法を用いた実装

以下の内容が動的計画法を用いた実装になる。

参考資料：
動的計画法（Dynamic Programming）をサルでも分かるように説明する – その１（フィボナッチ数列） – ベルリンのITスタートアップで働くソフトウェアエンジニアのブログ (jabba.cloud)

result=[0]
  for i in range(10000,1)
  result.push(0)
end for

fib=function(n=1)
  if n<=1 then
    return n
  else if result[n] != 0 then
    return result[n]
  else
    result[n] = fib(n-2) + fib(n-1)
    return result[n]
  end if
end function

print fib(50)

結果としては、1秒未満で出力された。
相当重複してる計算結果があったんだなあ、と思う。

動的計画法の採用条件

ただ、この動的計画法も「特定のシチュエーションにのみ採用できる」類のものなので注意。
具体的には、以下の条件かな、と。

  • 参照する配列内の値が0であることを許容できないと使えない（もしくは初期化の値を定義する
  • 参照する配列の範囲をあらかじめ決めておく必要がある（mapにするなら問題ないと思うけどメモリと処理くうかもしれない

まぁ万能な処理速度改善アルゴリズムがあれば今使われてるはずなので想定どおりではある。

アルゴリズムも場合によって使い分けましょうという結論になりそう。

136