Rubyで任意のメソッドをメモ化する

Rubyベストプラクティスの5-4より．メタプログラミングの例として面白かったのでまとめてみる．

メモ化とは

メモ化とは，引数に対するメソッドの戻り値を保存しておき，再び同じ引数でメソッドが呼び出された時にその値を再利用することにより，同じ計算を何度もすることを防ぐ最適化手法のひとつ．全ての引数に対しメソッドの結果が不変の場合(同じ引数で何度呼び出しても毎回同じ戻り値を返す場合)，メソッドをメモ化することができる．

以下はフィボナッチ数を再帰で計算するメソッドfibの例．

def fib(n) (0..1).include?(n) ? n : fib(n-2) + fib(n-1); end

この実装の場合，例えばfib(n)はn = 3で5回，n = 4で9回というように，nの値が大きくなるにつれて再帰呼び出し回数がどんどん増え，実行時間が爆発的に増大してしまう．私の環境だとfib(30)あたりからつらい．

これに対し，戻り値を保持して再利用するようにしたメモ化バージョンがこちら．

def fib(n)
  @cache ||= []
  @cache[n] ||= (0..1).include?(n) ? n : fib(n-2) + fib(n-1);
end

同じfib(m) (m <= n)の計算を何度も行うことを防ぎ，計算量の増大を抑えている．これならfib(1000)でも一瞬で計算できる．

module Memoizable

Rubyベストプラクティスにも以上のようにメモ化を自前で実装する方法についての説明があったが，それに加えて任意のメソッドをメモ化するためのモジュールMemoizableの紹介が載っていた(RubyGemsのパッケージではないみたい)．

memoizable.rb

# -*- coding: utf-8 -*-

module Memoizable
  def memoize(name, cache = Hash.new)
    original = "__unmemoized_#{name}__"
    
    ([Class, Module].include?(self.class) ? self : self.class).class_eval do
      alias_method original, name
      private      original
      define_method(name) { |*args| cache[args] ||= send(original, *args) }
    end 
  end 
end

使い方は簡単．Memoizableをincludeし，memoizeにメモ化したいメソッド名をSymbolで渡すだけ．

require "meoizable"
include Memoizable

def fib(n) (0..1).include?(n) ? n : fib(n-2) + fib(n-1); end

# メモ化
memoize :fib

# 一瞬で計算できる
fib(1000)

これだけで任意の既存メソッドをメモ化することができる．すごいすごい．

動作実験 (フィボナッチ数)

早速フィボナッチ数を計算するメソッドを作り，オリジナル版(fib1)とメモ化版(fib2)で速度比較をしてみた．

fib.rb

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-

require "benchmark"
require "memoizable"

include Memoizable

# フィボナッチ数 (再帰により実装)
def fib1(n) (0..1).include?(n) ? n : fib1(n-2) + fib1(n-1); end
def fib2(n) (0..1).include?(n) ? n : fib2(n-2) + fib2(n-1); end

# fib2のみメモ化
memoize :fib2

# fib(35)を計算
Benchmark.bmbm do |x|
  x.report("fib (original)") do
    fib1(35)
  end

  x.report("fib (memoized)") do
    fib2(35)
  end
end

実行結果 (Ruby 1.9.1)

Rehearsal --------------------------------------------------
fib (original)   9.720000   0.040000   9.760000 ( 10.254907)
fib (memoized)   0.000000   0.000000   0.000000 (  0.000298)
----------------------------------------- total: 9.760000sec

                     user     system      total        real
fib (original)   9.710000   0.020000   9.730000 (  9.969668)
fib (memoized)   0.000000   0.000000   0.000000 (  0.000018)

素晴らしい．
ちなみにこのMemoizableと同じような機能を持つRubyGemsパッケージとしてmemoizeというものが公開されている．使い方は上述のMemoizableとほぼ同じ．

おまけ

実行結果 (Ruby 1.8.7)

Rehearsal --------------------------------------------------
fib (original)  29.450000   0.070000  29.520000 ( 30.621650)
fib (memoized)   0.000000   0.000000   0.000000 (  0.000466)
---------------------------------------- total: 29.520000sec

                     user     system      total        real
fib (original)  29.390000   0.080000  29.470000 ( 30.837320)
fib (memoized)   0.000000   0.000000   0.000000 (  0.000017)

明らかにRuby 1.9の方が速い．やはりこれからは積極的にRuby 1.9以降を使うべきだと思う．