RubyのHash.default_procを用いたメモ化再帰

アルゴリズムの世界では単純に再帰関数を作成すると、計算量が莫大になってしまい、現実的な時間で解けないことが多々ある。それを解決する方法として、動的計画法とメモ化再帰という方法が有名である。

例としてフィボナッチ数を計算するプログラムで単純な再帰実装とメモ化再帰の違いを確認する。

fibonacci.rb

class FibonacciCalculator
  def calc(number)
    if number < 2 then
      return number
    else
      return calc(number - 1) + calc(number - 2)
    end
  end
end

calculator = FibonacciCalculator.new
puts calculator.calc(ARGV[0].to_i)

単純な再帰で実装した例である。たとえば、10番目のフィボナッチ数を計算する場合

1. calc(5) = calc(4) + calc(3)
   1. calc(4) = calc(3) + calc(2)
      1. calc(3) = calc(2) + calc(1)
         2. calc(2) = calc(1) + calc(0) = 1
      2. calc(2) = calc(1) + calc(0) = 1
   2. calc(3) = calc(2) + calc(1)
      1. calc(2) = calc(1) + calc(0) = 1

n = 5の場合に実に7回も再帰呼び出しを行うことになる。少し面倒だが6の場合は

1. calc(6) = calc(5) + calc(4)
   1. calc(5) = calc(4) + calc(3)
      1. calc(4) = calc(3) + calc(2)
         1. calc(3) = calc(2) + calc(1)
            2. calc(2) = calc(1) + calc(0) = 1
         2. calc(2) = calc(1) + calc(0) = 1
      2. calc(3) = calc(2) + calc(1)
         1. calc(2) = calc(1) + calc(0) = 1
   2. calc(4) = calc(3) + calc(2)
      1. calc(3) = calc(2) + calc(1)
         2. calc(2) = calc(1) + calc(0) = 1
      2. calc(2) = calc(1) + calc(0) = 1

実に12回の計算を行うことになる。このことからわかるように
n番目のフィボナッチ数の計算回数 = 1 + n-1番目のフィボナッチ数の計算回数 + n-2番目のフィボナッチ数の計算回数
と、計算回数自体がフィボナッチ数を上回る勢いで増えていく。これでは、数字が大きくなると現実的な時間では計算できないのは明らかである。

そこで、下記に示すように計算結果をキャッシュするメモ化再帰という手段がある。今回は計算結果のキャッシュ方法として、Hash.default_procを用いてみた。
(そもそも、この記事を書こうと思った理由が、Hash.default_procのような機能を他の言語では見かけたことがなく、自分で実装せずにメモ化できるというのが超便利だな！と感動したので、という感じ)

fibonacciCash.rb

class FibonacciCalculator
  def initialize
    @fibonacciCash = Hash.new
    @fibonacciCash.default_proc = -> (hash, key) { hash[key] = calc(key) }
  end

  def calc(number)
    if number < 2 then
      return number
    else
      return @fibonacciCash[number - 1] + @fibonacciCash[number - 2]
    end
  end
end

calculator = FibonacciCalculator.new
puts calculator.calc(ARGV[0].to_i)

n = 6の場合の計算回数は

1. calc(6) = calc(5) + calc(4)
   1. calc(5) = calc(4) + calc(3)
      1. calc(4) = calc(3) + calc(2) -> cashされる
         1. calc(3) = calc(2) + calc(1) -> cashされる
            2. calc(2) = calc(1) + calc(0) = 1 -> cashされる
         2. calc(2) = 1 <- cashされているので計算不要
      2. calc(3) = 2 <- cashされているので計算不要
   2. calc(4) = 3 <- cashされているので計算不要

各nに対して1度しか計算が必要ないので、n番目を計算するのに計算回数はn-1回しか必要ない。圧倒的に計算回数が節約される！

動的計画法に関しては次回かなー