フィボナッチ数計算の効率化

さて、前ページで作成した再帰的なfibonacciメソッドは効率が悪く、40番目のフィボナッチ数を求めるだけで筆者の環境では約20秒かかってしまいます(計算結果をメモ化することで多少速くなりますが)。そこで、ループで回して先端値を更新していき、nに達したら止めるロジックに変更します。

テストを書いていると、安心して実装をごっそりリファクタリングすることができます。

こうすれば必要な回数分だけloopを回してcurrent(とprev)を更新していくだけで済むので、使用するメモリが爆発することもありません。テストが通ることを確認します。

無事通過しました。n = 40まで含まれるテストケースがわずか0.001秒で終了しており、速度が改善されたことがわかります。このアルゴリズムなら、n = 100000 程度までなら1秒以内に結果が返ってきます。

以上

以上で今回の記事は終わりです。最後にTDDを紹介しましたが、テストコードによって正しいことが保証されながらプログラムが組み上がって行く様子を見るのは、なかなか爽快です。

前回のRSpec記事、今回のminitest記事でテストの概念に触れた初学者で「テストするようなコード書いてないし…」という人は、ちょっとしたプログラムをTDDで作ってみると新しい発見があるかもしれません。