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することで高速化できないだろうか？
