[Ruby] MemoizationのRubyによる高機能な実装Memoizeを作った。

Memoize

(src) memoize-0.1.0.tgz

gemだと敷居が高い事も十分に承知なのでページ下部にソースコードも晒しておきます。ご自由にご利用ください。

MemoizationはDonald Michieにより1968年に作られた言葉でその歴史は古い。最初の実装はCommon Lispのようだ。(参照: Wikipedia - Memoization) 既に十分に古い概念なのでRubyにもMemoizationの実装は存在するが随分と低機能で無駄なIOが発生するので高機能なMemoizationの実装をつくった。

Memoizationは簡単に言えば次のような機能である。

• 関数呼び出しの結果を引数をキーにして保存する。
• 元の関数をキャッシュが存在すればキャッシュを返しキャッシュが存在しない場合には値を導出してからキャッシュするように再定義する。

つまり、グローバル変数の値に実行結果が依存したり同じ引数を与えても実行の度に結果が変化するような副作用を伴う関数にはmemoizationを適用することはできない。また、通常のメソッドに余分なロジックを付加してメソッドを再定義するため極端にロジックの少ないメソッドでは逆に速度が遅くなる。

Memoizedするのに向いている関数(メソッド)は次のような性質を持つ。

• 深い再帰を持つなど同じ引数で何度も同じ関数の呼び出し行われる。


• 副作用を持たず、関数の実行コストが高いような関数。

Memoizationを実装するには、動的な関数定義を言語レベルでサポートしている必要がある。VHLLなRubyなら何の問題もない。今回実装したMemoizeは次のような機能をサポートしている。

• memoizedデータを保存するストレージをプログラマが独自に実装できる。
• トップレベル(main)だけでなく任意のスコープのメソッドをMemoizedできる。
• 永続化させるためのmemoizeデータのファイルへの書き出しはプログラム終了時だけである。

TODO

• スレッドセーフでない。

インストール

% wget http://rubyforge.org/frs/download.php/21051/memoize-0.1.0.gem
% sudo install Memoize-0.1.0.gem

Memoizedを使用したサンプルコード
Memoize.registerやMemoize.unmemoizeの第一引数に渡すselfはおまじないだと思ってください。トップレベルのmainへの参照を別のスコープから取得する方法がわからなかったのでこうなっています。知っている方がいたら教えていただけると助かります。

memoizeした関数を別の名前で参照したい際には、Memoize.registerの第三引数に:as => newmethodを指定する。

require 'memoize'
require 'benchmark'

def fib(n)
  return 1 if n < 2
  fib(n-1) + fib(n-2)
end

class Math2
  def self.fib(n)
    return 1 if n < 2
    fib(n-1) + fib(n-2)
  end
end

Benchmark.bm do |b|
  b.report("fib(30): ") { fib(30) }
  Memoize.register(self, 'fib')
  b.report("fib(30) with memoize") { fib(30) }
  b.report("fib(30) with memoize") { fib(30) }
  Memoize.unmemoize(self, 'fib')
end

Benchmark.bm do |b|
  Memoize.register(self, 'fib', :as => 'fastfib')
  b.report("fastfib(30) with memoize") { fastfib(30) }
  b.report("fastfib(30) with memoize") { fastfib(30) }
  Memoize.unmemoize(self, 'fastfib')
end

Benchmark.bm do |b|
  b.report("fib(30): ") { Math2.fib(30) }
  Memoize.register(self, 'Math2.fib')
  b.report("fib(30) with memoize") { Math2.fib(30) }
  b.report("fib(30) with memoize") { Math2.fib(30) }
end

実行結果

% ruby test_memoize.rb                                                                              
 user     system      total        real
fib(30):   7.060000   3.320000  10.380000 ( 10.376117)
fib(30) with memoize  0.000000   0.000000   0.000000 (  0.000043)
fib(30) with memoize  0.000000   0.000000   0.000000 (  0.000065)
 user     system      total        real
fastfib(30) with memoize  0.000000   0.000000   0.000000 (  0.000024)
fastfib(30) with memoize  0.000000   0.000000   0.000000 (  0.000023)
 user     system      total        real
fib(30):   6.380000   3.140000   9.520000 (  9.520442)
fib(30) with memoize  0.000000   0.000000   0.000000 (  0.000029)
fib(30) with memoize  0.000000   0.000000   0.000000 (  0.000024)
%

meoizedデータを保存するストレージの仕様
初めに書いたようにユーザ定義のストレージも使用できる。Memoize.registerに何も指定しない場合は、メモリ領域でデータを管理し、データを永続化させるために、プログラムの終了時にローカルのファイルシステムを使用してファイルとして書き込む。このファイルは/tmp以下に関数名をBase64エンコードしたファイル名.cacheで書き出される。

独自のストレージの実装
独自ストレージの実装はMemoize::Storableクラスを継承して以下の用に必要なメソッドを定義すればよい。詳しくは、lib/memoize.rb中のコメントを参照してください。MemCacheをストレージとして利用するクラスは次のように実装できる。

定義したストレージを使用するには、Memoize.registerの第三引数に:storeオプションを指定する。

class MemCacheStore < Memoize::Storable
attr_accessor :cache, :keys
def initialize(name)
  @keys   = []
  @cache  = MemCache.new 'localhost:11211', :namespace => 'rakuto.blogspot.com'
end

def get(key)
  @cache.get(key)
end

def set(key, value)
  @keys << key unless @keys.include?(key)
  @cache.set(key, value)
end

def delete(key)
  @cache.delete(key)
end

def delete_all
  @keys.each { |key| @cache.delete(key) }
end
end


Memoize.register(self, 'fib', :store => MemCacheStore)
fib(30)

ソースコード: memoize.rb
memoize-0.1.0.tgz

# Memoize is implementation Memoization for Ruby, this techinique to make functions faster.
#
# == Caveats:
# * Do not memoize a function whose behaviou depends on program state.
# * Do not memoize a function with side effects.
# * Do not memoize a function that returns a data structure that is modified by it's caller.
#
# Copyright 2007 rakuto under MIT licence.
# Rakuto Furutani <rakuto at gmail.com>
#
# == See: 
# Memoization - http://en.wikipedia.org/wiki/Memoization
#
module Memoize
  VERSION = '0.1.0'
  @@stores = {}

  # Memoize::Storable class is abstract class. You must implement class which memoization data is saved.
  # This module offer two storage class.
  #
  # * Memoize::MemoryStore -
  # * Memoize::PStore - Persisten cache support.
  #
  class Storable
    # {{{
    attr_accessor :store

    def initialize(name)
      raise "Memoize::Strable don't instantiage for abstract class."
    end

    def set(key, value)
    end

    def get(key)
    end

    def update(key)
    end

    def delete(key)
    end

    def delete_all
    end
    # }}}
  end

  # MemoryStore is class which store memoization data to memory.
  class MemoryStore < Memoize::Storable
    # {{{
    attr_accessor :store

    def initialize
      @store = {}
    end

    def get(key)
      @store[key]
    end

    def set(key, value)
      @store[key] = value
    end

    def delete(key)
      @store.delete(key)
    end

    def delete_all
      @store = {}
    end
    # }}}
  end

  # PStore is class which store memoization data with local file system.
  # This store class be able to use persistent cache, because this class write out 
  # cache data on file when process is exit.
  class PStore < Memoize::MemoryStore
    # {{{
    attr_accessor :store
    PREFIX_SAVE_FILE_DIR  = "/tmp"
    SUFFIX_SAVE_FILE_EXT  = ".cache" 

    def initialize(name)
      @name = name
      filename = encoded_filename(@name)
      begin
        if File.exists?(filename)
          File.open(filename, "rb") do |io|
            @store = Marshal.load(io)
          end
        else
          @store = {}
        end
      rescue
        @store = {}
      end
      # Write out cache 
      at_exit {
        File.open("#{filename}", "wb+") do |io|
          io.flock(File::LOCK_EX)
          Marshal.dump(@store, io)
          io.flock(File::LOCK_UN)
        end
      }
    end

    # Delete all memoized data and persisten cache fille
    def delete_all
      filename = encoded_filename(@name)
      File.exists?(filename) && File.unlink(filename)
      @store = {}
    end

    private 
    # Get the encoded file name
    def encoded_filename(name)
      File.join(PREFIX_SAVE_FILE_DIR, [name].pack('m').chomp+SUFFIX_SAVE_FILE_EXT)
    end
    # }}}
  end

  module_function
  # Make memoized function.
  #
  # Parameters:
  # * klass - You must surely specify 'self'. This parameter used to overwrite Toplevell function and 
  #           register as toplevel function. I need to think better the means ;)
  # * name - an memorized function name. 
  # * options - an specify options. <tt>:as</tt> is memorized function name, default is the same second arguments value.
  #             <tt>:store</tt> is specify class which store memorized data.
  #
  # == Memoized function examples
  #   def fib(n)
  #     return 1 if n < 2
  #     fib(n-1) + fib(n-2)
  #   end
  #
  #   end
  #   Memoize.register(self, 'fib')
  #   fib(30) # => 1346269 fast
  #   fib(30) # => 1346269 very fast
  #
  #   # Unmemorize
  #   Memoize.unmemoize(self, 'fib')
  #   fib(30) # => very slow
  #
  # == Memoized one Object methods  
  #   class Math2
  #     def self.fib(N)
  #       return 1 if n < 2
  #       fib(n-1) + fib(n-2)
  #     end
  #   end
  #
  #   Memoize.memorize(self, 'Math2.fib')
  #   Math.fib(30) # => fast
  #   Math.fib(30) # => very fast
  #   Memoize.unmemoize(self, 'Math2.fib')
  #
  # == Custom storage 
  # You can use own memoized data storage, in doing so you must implementaion following method
  #
  # Method/Arity:
  # * initialize/1 - this is constructor
  # * get/1 - an get the cache data with key
  # * set/2 - an set the cache data with key and value
  # * delete/1 - an delete the cache data with key
  # * delete_all/0 - an delete all cache
  #
  # Following class is MemCache storage sample.
  #
  #   # Memoized data storage using MemCache
  #   require 'memcache'
  #
  #   class MemCacheStore < Memoize::Storable
  #     attr_accessor :cache, :keys
  #     def initialize(name)
  #       @keys   = []
  #       @cache  = MemCache.new 'localhost:11211', :namespace => 'rakuto.blogspot.com'
  #     end
  #
  #     def get(key)
  #       @cache.get(key)
  #     end
  #
  #     def set(key, value)
  #       @keys << key unless @keys.include?(key)
  #       @cache.set(key, value)
  #     end
  #
  #     def delete(key)
  #       @cache.delete(key)
  #     end
  #
  #     def delete_all
  #       @keys.each { |key| @cache.delete(key) }
  #     end
  #   end
  # 
  #   Memoize.register(self, 'fib', :store => MemCacheStore)
  #   fib(30) # => fast
  #   fib(30) # => fast
  #
  def register(klass, name, options={})
    ns = name.split(/::|\./)
    method, klass = ns.pop, (ns.empty? ? klass : Object.const_get(ns.join("::")))
    store     = options[:store].nil? ? PStore.new(name) : options[:store].new(name)
    as_method = options[:as] || method
    Memoize._set_store(name, store)
    (class<<klass;self;end).instance_eval do  # for Ruby1.9
      method_name           = "#{as_method}_without_memoize"
      memoized_method_name  = "#{as_method}_with_memoize"
      define_method(memoized_method_name) do |*args|
        store = Memoize._get_store(name)
        ret = store.get(args) 
        if ret.nil?
          ret = send(method_name, *args)
          store.set(args, ret)
        end
        ret
      end
      alias_method method_name, method 
      alias_method as_method, memoized_method_name
    end
  end

  # Specify unmemoize method.
  # If you delete persistent cache when set delete_all true.
  #
  # == Example
  #   Memoize.memoize(self, 'slow_func')
  #   slow_func(arg)
  #   Memoize.unmemoize(self, 'slow_func')
  # 
  def unmemoize(klass, name, delete_all=false)
    (class<<klass;self;end).class_eval do 
      undef_method("#{name}_with_memoize")
      alias_method name, "#{name}_without_memoize"
    end
    delete_all && @store.delete_all
  end

  # This method is public, but you don't need call directly. 
  def _set_store(name, store)
    @@stores[name] = store
  end

  # This method is public, but you don't need call directly. 
  def _get_store(name)
    @@stores[name]
  end

  # Not implemented
  module Expire
  end
end

if $0 == __FILE__
  def fib(n)
    return 1 if n < 2
    fib(n-1) + fib(n-2)
  end

  class Math2
    def self.fib(n)
      return 1 if n < 2
      fib(n-1) + fib(n-2)
    end
  end

  class MemCacheStore < Memoize::Storable
    attr_accessor :cache, :keys
    def initialize(name)
      @keys   = []
      @cache  = MemCache.new 'localhost:11211', :namespace => 'rakuto.blogspot.com'
    end

    def get(key)
      @cache.get(key)
    end

    def set(key, value)
      @keys << key unless @keys.include?(key)
      @cache.set(key, value)
    end

    def delete(key)
      @cache.delete(key)
    end

    def delete_all
      @keys.each { |key| @cache.delete(key) }
    end
  end


  Memoize.register(self, 'Math2.fib', :store => MemCacheStore)
  Benchmark.bm do |b|
    b.report("fib(30) with memoize: ") { Math2.fib(30) }
    #Memoize.unmemoize(self, 'fib')
    b.report("fib(30)") { Math2.fib(30) }
  end
end

考察

• Memoizaionのテクニックは関数型言語と非常に相性がよさそう。
• Railsのルーティング部分は副作用を含まないメソッド単位に分解して、Memoizedすることで高速化できないだろうか？