バックエンド

異なる実装によるフィボナッチ数列の第N項を返す速さ比べ

Photo credit unsplash-logo
Marc-Olivier Jodoin

フィボナッチ数列の第N項を返す速さ比べ

久しぶりの投稿になります、edihasam です。
最近お勉強の一環として、フィボナッチ数列を実装する場面があったので、実装の違いでどれくらい速度に差が出てくるのかをグラフにしました。

まずグラフをお見せした後、遅いものから早いものまで具体的なコードを公開します。

速さ比べをしたグラフ

1枚目のグラフ

各アルゴリズムで第25項までそれぞれ10回ずつ出力するというタスクをこなしたときのグラフです。再帰で実装したやつが遅すぎてメモ化を使ったやつが完全に隠れてしまっています。

2枚目のグラフ

再帰を除いたふたつについて、第100項から第1000項までをそれぞれ10回出力するというタスクをこなしたときのグラフです。繰り返しの方が遅くなることがわかりますが、しっかり線形時間で遅くなっていますね。対照的にメモ化を使用した方はほとんど定数時間で実行されているのでしょうか……驚きの速さですね。

具体的な実装

わかりやすいけど遅い実装

以下コードが最も遅い、しかしながら最も理解しやすい再帰的な定義に基づくフィボナッチ数列の第N項を返す実装です。

繰り返しを用いた実装

以下コードが二番目に速い、繰り返しを利用したフィボナッチ数列の第N項を返す実装です。

最も速いメモ化を使用した実装

以下コードが最も速い、メモ化を利用したフィボナッチ数列の第N項を返す実装です。