フィボナッチ数列の処理速度改善。
この記事はなに
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)
動的計画法を用いた実装
以下の内容が動的計画法を用いた実装になる。
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にするなら問題ないと思うけどメモリと処理くうかもしれない
まぁ万能な処理速度改善アルゴリズムがあれば今使われてるはずなので想定どおりではある。
アルゴリズムも場合によって使い分けましょうという結論になりそう。