Ruby でフィボナッチ数を計算する方法


Ruby で N 番目のフィボナッチ数を計算する方法と, フィボナッチ数列の Enumerator の一例を紹介します.

フィボナッチ数列の一番最初の数は 0 と 1 の場合の 2 パターンが存在しますが, 今回は 0 から始まるフィボナッチ数列を扱います.

つまりは次のような数列になります:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

N 番目のフィボナッチ数

まずは N 番目のフィボナッチ数を計算する方法から紹介します.

インデックスである N は 0 から始まるようにしますので 0 を指定すると 0, 1 だと 1, 2 だと 1, 3, だと 2 を返すようにします.

また 0 より小さい値を入力した場合, nil を返すようにします.

今回は 4 パターン紹介します.

再帰的に計算 1

def fibonacci1(n)
    return   if n < 0
    return n if n < 2
    fibonacci1(n - 1) + fibonacci1(n - 2)
end

fibonacci1 10  # => 55
fibonacci1 20  # => 6765
fibonacci1 30  # => 832040

一つ目の方法は, メソッドを再帰的に呼び出して計算する方法です.

お手軽ですが, 入力されるインデックス n の値が比較的少ない場合はいいですが, 多くなると急激に処理時間がかかることになりますので, 実用的ではないのでしょうね.

n10, 20, 30 の場合のベンチマークになります:

                   user     system      total        real
fibonacci1 10  0.000016   0.000002   0.000018 (  0.000015)
fibonacci1 20  0.001171   0.000001   0.001172 (  0.001173)
fibonacci1 30  0.140113   0.000211   0.140324 (  0.140560)

再帰的に計算 2

def fibonacci2(n)
  cache = {}
  l = lambda do |m|
    return   if m < 0
    return m if m < 2
    cache[m] ||= l[m - 1] + l[m - 2]
  end
  l.call(n)
end

一つ目の方法は目の方法のように再帰的に計算しますが, 計算結果を cache に保存するので, 同じ結果になる計算は省くことができ, 一つ目の方法とは比較にならないくらい早くなります.

ただ n10_000 など大きい数を入力すると stack level too deep (SystemStackError) と言う例外が発生するので, この方法も残念ながらあまり実用的ではないのかもしれません.

lambda を使っているのは cachelambda の中から参照できて書き換えることができるからです.

そのようなことが可能なのは lambda がクロージャだからです.

ベンチマークになります:

                   user     system      total        real
fibonacci2 10  0.000015   0.000001   0.000016 (  0.000015)
fibonacci2 20  0.000015   0.000001   0.000016 (  0.000016)
fibonacci2 30  0.000043   0.000001   0.000044 (  0.000044)

Hash.new で計算

def fibonacci3(n)
  return if n < 0
  Hash.new { |h, k| h[k] = k < 2 ? k : h[k - 1] + h[k - 2] }[n]
end

三つ目の方法はやや変わった方法ですが, この方法も一つ目二つ目の方法と同じ再帰的に計算する方法になります.

Hash.new はブロックを取ると, h にハッシュ, k にキーが渡され, ブロックの返り値がデフォルトの値になります.

なので例えば 10 というキーをそのハッシュに渡すと, それと対の値が設定されていないのでデフォルトの値がそのブロックの中で計算されるというわけです.

またブロックのローカル変数 hh[k] = k < 2 ? k : h[k - 1] + h[k - 2] の部分でどんどん k の時の値を保存していくので, 結果的に重複する計算をキャッシュできています.

こんな方法で計算もできちゃう Ruby 素敵です.

ただ残念ながら 10_000 のような大きい値を渡すと同様に SystemStackError という例外が発生するので, この方法もあまり実用的ではないのでしょう.

ベンチマークになります:

                   user     system      total        real
fibonacci3 10  0.000012   0.000001   0.000013 (  0.000013)
fibonacci3 20  0.000015   0.000002   0.000017 (  0.000017)
fibonacci3 30  0.000029   0.000004   0.000033 (  0.000033)

パラレルアサインメイントで計算

def fibonacci4(n)
  return   if n < 0
  return n if n < 2
  a, b = 0, 1
  n.times { a, b = b, a + b }
  a
end

四つ目の方法は, パラレルアサインメントを使って計算していく方法になります.

パラレルアサインメントの部分は a, b = 0, 1a, b = b, a + b になります.

この方法は四則演算の足す計算を連続させていくので, 再帰的な方法に比べてシンプルです.

仮に 10_000 という値を与えても SystemStackError という例外は発生しません:

n = fibonacci4 10_000
n                      # => 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
n.to_s.size            # => 2090

#                        user     system      total        real
# fibonacci4 10_000  0.006450   0.000598   0.007048 (  0.007048)

計算時間は全くかからないのですが, その長さが少し大変です…

単純に変数がどの値まで保持できてどこまで計算できるかということになります.

なのでさらに大きな 1000**2 という値を n に与えても少し時間がかかりますが, 計算できてしまいます:

fibonacci4(1000**2).to_s.size  # => 208988

#                         user     system      total        real
# fibonacci4 1000**2 12.004170   2.244993  14.249163 ( 14.253972)

ただ計算結果のフィボナッチ数の文字列の長さが 208988 にもなってしまいますので, その計算結果の値を掲載してしまいますと, そちらの方が記事のメインコンテンツになり兼ねないので, 残念ながら控えさせていただきたいと思います.

10_0002090 文字ですからね. その約 100 倍です…

なので, そのように大きい数も扱えるこの方法は実用性があるのではないかと思います.

ベンチマークになります:

                   user     system      total        real
fibonacci4 10  0.000007   0.000002   0.000009 (  0.000006)
fibonacci4 20  0.000005   0.000001   0.000006 (  0.000005)
fibonacci4 30  0.000005   0.000001   0.000006 (  0.000005)

それぞれのベンチマークの比較

これまで 4 つの方法を紹介しましたが, それぞれのベンチマークの比較になります.

n30 の場合:

                   user     system      total        real
fibonacci1 30  0.140178   0.000077   0.140255 (  0.140390)
fibonacci2 30  0.000042   0.000007   0.000049 (  0.000048)
fibonacci3 30  0.000023   0.000003   0.000026 (  0.000026)
fibonacci4 30  0.000008   0.000001   0.000009 (  0.000008)

n1_000 の場合:

                      user     system      total        real
fibonacci2 1_000  0.001378   0.000539   0.001917 (  0.001918)
fibonacci3 1_000  0.001463   0.000122   0.001585 (  0.001575)
fibonacci4 1_000  0.000520   0.000001   0.000521 (  0.000521)

fibonacci11_000 という値を渡してしまうと, 一向に計算が終わる気配がありませんでしたので比較対象から除外させていただきました.

この結果からわかるように再帰的な処理をしない fibonacci4 がもっとも早いですね.

フィボナッチ数列の Enumerator

今までのは全て N 番目のフィボナッチ数を計算する方法でしたが, 今度は Ruby の Enumerator クラスを使って, [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] のような連続したフィボナッチ数列を順々に取得する方法を紹介します:

def fibonacci_enumerator
  Enumerator.new do |y|
    a, b = 0, 1
    loop do
      y << a
      a, b = b, a + b
    end
  end
end

この方法は Ruby のドキュメントにも書かれているので, 一般的なのでしょう.

ただこちらのコードは 0 から始まるように少しだけ変更しております.

ブロックパラメータの y は “yielder” オブジェクトと呼ばれるもので, yield メソッドを呼ぶことで渡した値を産出することができます.

今回はその yield メソッドのエイリアス << を使っています.

使用例です:

fe = fibonacci_enumerator
fe.take 10  # => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
fe.next     # => 0
fe.next     # => 1
fe.next     # => 1
fe.next     # => 2
fe.next     # => 3
fe.next     # => 5
fe.next     # => 8
fe.next     # => 13
fe.next     # => 21
fe.next     # => 34

まとめ

今回は Ruby で N 番目のフィボナッチ数を計算する 4 パターンと, フィボナッチ数列を取得する Enumerator の一例を紹介させていただきました.

Ruby でフィボナッチ数を計算したいという時は参考にしていただけたら幸いです.

ところでフィボナッチ数列って自然界の様々な所に潜んでいて, 花の花びらの数はフィボナッチ数というのは有名です.

あの有名な黄金比もフィボナッチ数列と密接な関係性がありますし.

フィボナッチ数列, 神秘的すぎます.

世界中の数学者やデザイナーの心を魅了してしまうのも頷けます.

Ruby を通してその一端に触れることができて僕はささやかな幸せを感じておりますw

最後までお読みくださいましてありがとうござしました.