Rubyでフィボナッチ数列を出力する

こんにちは、Ruby歴半年のプログラマです。

基本的なアルゴリズムを習得したいと考えて、『Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量』を読んでいます。

本記事は『Pythonではじめるアルゴリズム入門』のPythonのフィボナッチ数列のサンプルコードをRubyで実装しました。

より良いコードの書き方などありましたら教えてもらえると嬉しいです。

環境

$ sw_vers
ProductName:    Mac OS X
ProductVersion: 10.15.4
BuildVersion:   19E287
$ ruby -v
ruby 2.7.0p0 (2019-12-25 revision 647ee6f091) [x86_64-darwin19]

Rubyで再帰を使ったフィボナッチ数列

2020年4月15日追記 @superrino130 さん @scivola さん より、memo がメソッド内に定義されているのでメモの意味がないとのご指摘をいただきましたので、実装を修正しました。なお修正前と修正後のベンチマークを計測しました。

@memo = { 1=> 1, 2=> 1 }
def fibonacci(input)
  return @memo[input] if @memo
  @memo[input] = fibonacci(input - 2) + fibonacci(input - 1)
end

fibonacci(10)
# -> 55

例外条件(メモにすでにキーが含まれているか)を確認して、例外条件に合致すればそのバリューを返す、ガード節を定義しています。

return memo[input] if memo.has_key?(input)

メモ化の効果を測定するベンチマーク

require 'benchmark'

n = 35
Benchmark.bm(7) do |x|
  x.report("memo") {
    # 修正前(メモがメソッドの定義内なので効果なし)
    def fibonacci(input)
      memo = { 1=> 1, 2=> 1 }
      return memo[input] if memo.has_key?(input)
      memo[input] = fibonacci(input - 2) + fibonacci(input - 1)
    end
    fibonacci(n)
  }
  x.report("@memo") {
    # 修正後(メモがメソッドのスコープ外なので効果あり)
    @memo = { 1=> 1, 2=> 1 }
    def fibonacci(input)
      return @memo[input] if @memo
      @memo[input] = fibonacci(input - 2) + fibonacci(input - 1)
    end
    fibonacci(n)
  }
end

memo      2.580194   0.025784   2.605978 (  3.037780)
@memo     0.000006   0.000001   0.000007 (  0.000007)

参考

• Ruby でベンチマークを取る方法
• Benchmark.#bm
• benchmark-driver

Rubyでループを使ったフィボナッチ数列

def fibonacci(input)
  (2...input).inject([1, 1]){ |memo, number|
    memo << (memo[number - 2] + memo[number - 1])
  }
end

p fibonacci(10)
# -> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

初期値を用意して畳み込みの演算ができるEnumerable#injectを使っています。