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
の値が比較的少ない場合はいいですが, 多くなると急激に処理時間がかかることになりますので, 実用的ではないのでしょうね.
n
が 10
, 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
に保存するので, 同じ結果になる計算は省くことができ, 一つ目の方法とは比較にならないくらい早くなります.
ただ n
を 10_000
など大きい数を入力すると stack level too deep (SystemStackError)
と言う例外が発生するので, この方法も残念ながらあまり実用的ではないのかもしれません.
lambda
を使っているのは cache
を lambda
の中から参照できて書き換えることができるからです.
そのようなことが可能なのは 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
というキーをそのハッシュに渡すと, それと対の値が設定されていないのでデフォルトの値がそのブロックの中で計算されるというわけです.
またブロックのローカル変数 h
に h[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, 1
と a, 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_000
で 2090
文字ですからね. その約 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 つの方法を紹介しましたが, それぞれのベンチマークの比較になります.
n
が 30
の場合:
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)
n
が 1_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)
fibonacci1
で 1_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
最後までお読みくださいましてありがとうござしました.
関連記事
Ruby の正規表現を備忘録としてまとめてみた2018.08.30
Ruby の関数プログラミングでオイラー積を計算してみた2018.07.02
Ruby のブロック, Proc, Lambda の違い2018.06.21
Ruby の StandardError でどういう間違いをすると, どの例外が発生するのかのメモ2018.07.13
Ruby の正規表現で素数かどうかを確認する方法2018.09.11