BETA

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

投稿日:2019-01-31
最終更新:2019-01-31
※この記事は外部サイト(https://mittsu-blog.com/compare-fib-algori...)からのクロス投稿です

画像が貼り付けられなかったのでブログで見てください!

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

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

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

速さ比べをしたグラフ

1枚目のグラフ

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

2枚目のグラフ

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

具体的な実装

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

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

def recursive_fib(n):  
    if n == 0 or n == 1:  
        return 1  
    else:  
        return recursive_fib(n-1) + recursive_fib(n-2)

繰り返しを用いた実装

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

def repetition_fib(n):  
    result = 0  
    f0 = 0  
    f1 = 1  
    for i in range(n):  
        result = f0 + f1  
        f0 = f1  
        f1 = result  
    return result

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

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

def memo_fib(n, memo={}):  
    if n == 0 or n == 1:  
        return 1  
    try:  
        return memo[n]  
    except KeyError:  
        result = memo_fib(n-1, memo) + memo_fib(n-2, memo)  
        memo[n] = result  
        return result
技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

@edihasamの技術ブログ

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう
目次をみる
技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
or 外部アカウントではじめる
10秒で技術ブログが作れます!