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

この記事はなに

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にするなら問題ないと思うけどメモリと処理くうかもしれない）後述

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

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

20210305追記

試しにmapを使って動的計画法を実装してみたところ、動作がやたら遅いことが発覚。
どちらかというとmapによるメモリアクセスがネックになってんのかなーって思った。

関数内で動的確保してる変数分のメモリが原因かな？と思ってグローバル変数として使いまわしてみたものの、結果は同じ。
すなわちmapの処理自体に時間がかかっていることになる。

あとこの挿入だと割とメモリ断片化が起きてしまうのでは？とも思った。
いずれにしてもこういう高負荷をかける動作でmapは使わないほうがよさそう。

（文字列データを控えておくとかあらかじめ確保しておくケースだとアリだと思うので、
ケースごとに利用方法を考えていくのがいい）

参考程度に5分くらいで書いたコードを残しておく。

//map_program

result={}
tmp=0

fib=function(n=1)
  if n<=1 then
    return n
  else if result.hasIndex(n) != 0 then
    return result[n]
  else
    tmp = fib(n-2) + fib(n-1)
    result = result + {n:tmp}
    return result[n]
  end if
end function

print fib(45)

150