【Ruby】フィボナッチ数列の問題をメモ化で解く

はじめに

今回はフィボナッチ数列を求めるプログラムをメモ化により高速化することを目指します！

フィボナッチ数列とは

最初の二項が1で，第三項以降の項がすべて直前の二項の和になっている数列のこと．
例）1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

メモ化とは

プログラムの高速化における最適化技法の一種で，計算結果を保持しておくことにより，再計算を防ぐ手法です．

もっと簡単に言うと，一度計算したものはメモしておいて，必要であれば再利用しようというものです．

次節以降では，第五十項までのフィボナッチ数列を求めるプログラムを基に，メモ化を利用することで，実行速度をどれだけ短縮できるか検証します．

愚直に書くフィボナッチ数列

require 'benchmark'

def getFibonacciNumber(n)
  if n < 0
    return -1
  elsif n == 0 || n == 1
    return 1
  else
    return getFibonacciNumber(n-1) + getFibonacciNumber(n-2)
  end
end


Benchmark.bm 10 do |r|
  r.report "No Memorization" do   
    0.upto(50) do |i|
      printf("\n%4d:%d", i, getFibonacciNumber(i))
    end
  end
end

再帰関数により，毎回第一項から順に計算しています．
したがって，第一項から第五十項まで求めるのに 6455.837074秒 かかります．

メモ化を用いたフィボナッチ数列

require "benchmark"

class FibonacciNumber

  def initialize()
    @aryFibNum = Array.new()
    @aryFibNum = [1, 1]
  end

  def getFibonacciNumber(n)
    if (@aryFibNum.size - 1) < n then
      @aryFibNum << @aryFibNum[n - 1] + @aryFibNum[n - 2]
      return @aryFibNum[n]
    else
      return @aryFibNum[n]
    end
  end

end


fn = FibonacciNumber.new
Benchmark.bm 10 do |r|  
  r.report "Memorization" do   
    0.upto(50) do |i|
      printf("\n%4d:%d", i, fn.getFibonacciNumber(i))
    end
  end
end

メモ化により，一度計算した項は保持しておくようにします．
そして，保持しておいた数値を再利用することで計算時間の短縮を実現します．

ベンチマークの結果は，第一項から第五十項まで求めるのに 0.000218秒 であり，計算時間の大幅な短縮を実現したことが分かります！

おわりに

メモ化はプロコンや就活の技術テストでもよく見受けられるキーワードなので，勉強しておいて損はないです．

（本記事に関して，プログラムや説明でこうした方がいいなどありましたら，コメントよろしくお願いします！）