Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
12
Help us understand the problem. What is going on with this article?
@bloody_snow

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

More than 5 years have passed since last update.

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

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

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)
        1. 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)
          1. 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)
        1. 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される
          1. 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回しか必要ない。圧倒的に計算回数が節約される!

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

12
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
m3dev
インターネット、最新IT技術を活用し日本・世界の医療を改善することを目指します

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
12
Help us understand the problem. What is going on with this article?