メモ化から学ぶ早期リターン

お世話になっている方からの課題

業務の合間でようやく手をつけられたので、ここにその奮闘記を記す。数学、勉強しなければならないという思いが強まった今日この頃です。

指令:フィボナッチ数列のマトリクスを作るメソッドを再帰処理を用いて作りあげよ

マトリクス部分も実装はできているのですが、今回はトピックには関係がないので、割愛します。
最初、自分がこれ作った時は、再帰処理を利用していないものだったので、頭を悩ませたんですが、結構再帰処理の例としてよくフィボナッチ数列使われるんですねぇ・・・

def calc_fibonacci 
  array = [0,1]
  (1..(@fields * @records)).each do |index|
    fibo_num = array[index - 1] + array[index]
    array.push(fibo_num)
  end
end

上記が再帰を使わない自分の最初のフィボナッチメソッドなんですが隣り合う数字の和が次の数字となるのならば、ループさせている変数の片方を-1してやれば、隣り合う数字の和という式を実現できる発想でした。

再帰使えよ・・・再帰使えよおおおおおおぉぉぉぉ！！！

というわけで、再帰を考えていきます。

fibo.rb

index calc_fibonacci
when 0 then
  0
when 1 then
  1
else
  calc_fibonacci(index - 2) + calc_fibonacci(index - 1)
end

これが再帰処理になります。おい、なんだindexって、変数ねぇぞと思うかもしれませんが、これは、まだ未完成のコードです。ここからメモ化の実装を入れていきますが、その前に再帰についての説明をします。

再帰処理

コマンドオプションにもよくある-rのことです。recursiveですね。一旦最深部まで降りて登ってくるイメージです。例えば、rmコマンドも再帰オプションを使うと、削除対象がディレクトリの深いものだと一旦最深部まで降り、そこから削除を開始して最後に一番最初のディレクトリを消去する挙動をとります。
最初の再起を使っていないメソッドはフィボナッチ数を全て出してくれるのと違って、この再帰を使ったメソッドはn番目のフィボナッチ数を出してくれるものです。
入力に対する求めることができるモノが違います。しかし、どちらのメソッドを用いてもマトリクスを作ることはできます。この辺、面白いと感じます。
求め方、実装の仕方、つまり、中身は違うけど、求められているものは求めることができる、数学っぽいですね。エンジニアとしても非常に大事なことです。
関数の中に同じ関数があるので、引数が計算されると0か1が得られるまで何度も計算がなされて、その分岐された最終結果が加算されることでフィボナッチ数が求められるというものです。

メモ化

ですが、このコード、重複計算が多く、引数の数が大きくなればなるほどメソッドのコール回数も増えるので、時間がかかります。そこで、メモ化を実装します。

memo_fibo.rb

  @@memo = {}

  def calc_fibonacci(index)
    return @@memo[index] if @@memo.has_key?(index)

    @@memo[index] =
      case index
      when 0 then
        0
      when 1 then
        1
      else
        calc_fibonacci(index - 2) + calc_fibonacci(index - 1)
      end
    return @@memo[index]
  end

上から見ていきます。
haz_key?メソッドを用いて、配列indexの中に同じキーを持つバリューがあれば、trueを行い、その時点で処理を終了させるreturnが書かれています。
そして、その後に、先ほどのフィボナッチ数を求めていき、配列の中に処理結果を入れていけるように、case文そのものを配列に代入しています。ここ、個人的に驚いたのですが、式ならば代入可能、確かにそうですが、＝で結べる視点が横にしかなかった（x = 0のような）ので、ここでの視点は縦なんですよね。

x = 
case index
when
.
.
when
.
.

コードを読む視点の高さを1個手に入れた感がありました。式ならば、いくら長くてもその結果を代入できる。

再帰的に一度計算した結果が配列のなかにあれば、処理を終わらしてくれて、無い時だけ、has_key?のfalseが返って、下の処理が走るようになる実装がコードの最初になされているので、重複されている計算がされず、結果として、高速化できます。

早期リターン

この時の、条件が満たされている時には、処理を終わらせる、つまりそれ以下に書かれた処理は実行されないようにすることで、ifのネストや、else句の記述量を増加させないようにするテクニックを、早期リターンと呼びます。