はじめに
Ruby で竹内関数をメモ化によって、高速にしようとあれこれやります。
竹内関数とは
これです。Ruby で書くとこんな感じです。
def tarai(x, y, z)
return y if x <= y
tarai(
tarai(x - 1, y, z),
tarai(y - 1, z, x),
tarai(z - 1, x, y)
)
end
引数をたらい回しにして、再帰しまくることにより、重い処理になっています。
迂闊に、
tarai(30, 15, 0)
とかすると、後悔します。
メモ化とは
竹内関数が遅いのは、引数をたらい回しにして再帰的に関数を実行することで、引数が同じなのに、何度もなんども同じ計算をしなければならないためです。
そこで、ある引数の組合せで計算を一度してしまえば、その答えをメモしておいて、もう一度同じ引数の計算をしなければならなくなった時に、実際に計算するのでなく、メモに記録した答えを返すようにすることで、速く答えを出す、というものです。
で、何をしようというの？
Fibonacci 数を求める fibo(n) のように引数がひとつの時には、特に問題はありません。
def make_fibo
cache = {}
fibo = lambda do |n|
return n if n < 2
cache[n] ||= fibo.call(n - 2) + fibo.call(n - 1)
end
end
fibo = make_fibo
fibo.call(100)
すればＯＫです。
ここでは、計算結果を、引数をキーにした Hash オブジェクト cache にメモしています。ちなみに、cache をグローバル変数にしたくないので、lambda を使ってクロージャを作っています。
def ... end で囲まれた空間は、局所変数の独立した 名前空間 を作るので、def で作ったメソッドは外側の局所変数をキャプチャーできず、クロージャにはなりません。
その代わり、lambda 等を使ってクロージャを作る時には、def ... end の中は、局所変数に関してはクリーンルームになるので、クロージャを返すメソッドを作った上で、クロージャを作るのがオススメのはずです。多分。
話が飛んでしまいましたが、Fibonacci の場合と違い、竹内関数の場合、引数が３つあります。これをどう Hash オブジェクトに登録するかです。
Python ならどうするか
Python なら、当然引数を tuple にして、dict オブジェクトに登録するはずです。
まずは、クロージャを使って、
def make_tarai:
cache = {}
def tarai(x, y, z):
if x <= y:
return y
key = (x, y, z)
val = cache.get(key)
if val is not None:
return val
val = tarai(
tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(z-1, x, y)
)
cache[key] = val
return val
return tarai
tarai = make_tarai()
tarai(100, 50, 0)
あるいは、Python のデフォルト引数は関数を定義した時に一度だけ評価されるので、
def tarai(x, y, z, cache={}):
if x <= y:
return y
key = x, y, z
val = cache.get(key)
if val is not None:
return val
val = tarai(
tarai(x-1, y, z, cache),
tarai(y-1, z, x, cache),
tarai(z-1, x, y, cache),
cache
)
cache[key] = val
return val
tarai(100, 50, 0)
でもＯＫでしょう。tarai 関数を何度実行しても、常に同じ dict オブジェクトが使われるので、一度計算結果をメモしてしまえば、次に tarai を実行した時にもそのメモが使えます。
手元で計算すると、tarai(100, 50, 0) で約0.03 秒程度です。
Ruby で同じようなことをすると
Rubyの場合、デフォルト引数はメソッドを実行するたびに評価されるので、Python と違い、メソッドを実行するたびに一からメモを取り直すことになってしまいます。
どちらがいいのか私にはよく分かりません。Python が変わっているような印象ですが、どちらが勝ちで、どちらが負けという話でないことは間違いなさそうです。
そういうわけで、Ruby の場所、クロージャでいきます。
Ruby には tuple がないので、配列でやるしかありません。
def make_tarai
cache = {}
tarai = lambda do |x, y, z|
return y if x <= y
cache[[x, y, z]] ||= tarai.call(
tarai.call(x - 1, y, z),
tarai.call(y - 1, z, x),
tarai.call(z - 1, x, y)
)
end
end
tarai = make_tarai
tarai.call(100, 50, 0)
できるにはできましたが、Python に比べると圧倒的に遅いです。手元で計算すると、0.09 秒前後かかってしまいました。完敗です。
def time
start = Time.now
result = yield
diff = Time.now - start
puts "Elapsed time: #{diff} secs"
p result
end
time { tarai.call(100, 50, 0) }
で時間を計算しましたが、以下略。
Python の tuple は見た目が同じなら同じオブジェクトです（少なくとも中身がintの場合）。なので高速に dict のキーを比較することができます。
それに対し、Ruby の配列は見た目が同じでも別のオブジェクトになりうるので、キーの比較に時間がかかってしまうのが大きな原因だと思います。
ここからが知恵の出しどころです。
計算結果を多重 Hash に登録する
配列をキーにするから遅いのなら、メモを多重 Hash にして、Integer である、個々のx, y, z をキーにして、計算結果をメモすることにします。
戦略的には、まず、引数 x のための cache_x = {} を用意します。
そして、cache_x[x] は引数 y のための Hash オブジェクト cache_y を返して欲しいのですが、引数 x が初見であれば nil が返ってきます。
そこで、cache_y = cache_x[x] ||= {} とすることで、x が初見の場合には、新たな Hash オブジェクトを cache_[x] に登録した上で、変数 cache_y に代入することができます。
そうすると、こんな感じになります。
def make_tarai
cache_x = {}
tarai = lambda do |x, y, z|
return y if x <= y
cache_y = cache_x[x] ||= {}
cache_z = cache_y[y] ||= {}
cache_z[z] ||= tarai.call(
tarai.call(x - 1, y, z),
tarai.call(y - 1, z, x),
tarai.call(z - 1, x, y)
)
end
end
tarai = make_tarai
tarai.call(100, 50, 0)
0.012 秒前後です。
やりました。Python に勝ちました。圧勝です。
ちなみに、Python でこの方法を使うと少し遅くなってしまいました。恐るべし、Python の tuple 。
しかし、Ruby が勝ったとはいえ、
cache_y = cache_x[x] ||= {}
cache_z = cache_y[y] ||= {}
cache_z[z] ||= tarai.call(...
の部分がまだだるいです。どうせなら cache[x][y][z] ||= tarai.call( ... としたいです。
Hash のデフォルト値を使う
Ruby の場合、
cache = Hash.new { |hash, key| hash[key] = {} }
とすることで、未登録のキーに出くわしたとき、新たな Hash オブジェクトを作って、そのキーに登録するような Hash オブジェクトを作ることができます。
これを多重にすればいいわけです。
def make_tarai
cache = Hash.new do |hash, key|
hash[key] = Hash.new do |hash, key|
hash[key] = {}
end
end
tarai = lambda do |x, y, z|
return y if x <= y
cache[x][y][z] = tarai.call(
tarai.call(x - 1, y, z),
tarai.call(y - 1, z, x),
tarai.call(z - 1, x, y)
)
end
end
tarai = make_tarai
tarai.call(100, 50, 0)
これでＯＫです。
とはいえ、この cache の定義もだるいです。何とかスマートにしたいものです。
そこで、cache の右辺をよく見ると、ラスボス的な {} を Hash.new { |hash, key| hash[key] = ... } でラップしていけば良さそうだと分かります。メタプログラミングで何とかしましょう。
メタプログラミング登場
方針としては、何重にもなった Hash.new {} の文字列を作って、eval することにします。
引数の数が３つの場合、{} を２回 Hash.new {} でラップすればいいから、メモ化する際の引数の数を arity とすると、
def make_cache(arity)
seed = "{}"
(arity - 1).times do
seed = "Hash.new { |hash, key| hash[key] = #{seed} }"
end
eval(seed)
end
この make_cache があれば、簡単に多重 Hash を作ることができます。
def make_cache(arity)
seed = "{}"
(arity - 1).times do
seed = "Hash.new { |hash, key| hash[key] = #{seed} }"
end
eval(seed)
end
def make_tarai
cache = make_cache(3)
tarai = lambda do |x, y, z|
return y if x <= y
cache[x][y][z] ||= tarai.call(
tarai.call(x - 1, y, z),
tarai.call(y - 1, z, x),
tarai.call(z - 1, x, y)
)
end
end
tarai = make_tarai
tarai.call(100, 50, 0)
かなりいい感じになりました。でも、もっと高速を目指したいです。
いろんな事情があって、Proc オブジェクトはメソッドより遅いと聞きます。そこで、Proc オブジェクトではなく、メソッドでクロージャを作ってみます。
メソッドでクロージャを作る
すでに述べたように、def でクロージャは作れません。そこで、def を使わずにメソッドを作ることにします。
define_method の登場です。
def make_cache(arity)
seed = "{}"
(arity - 1).times do
seed = "Hash.new { |hash, key| hash[key] = #{seed} }"
end
eval(seed)
end
def make_tarai
cache = make_cache(3)
define_method(:tarai) do |x, y, z|
return y if x <= y
cache[x][y][z] ||= tarai(
tarai(x - 1, y, z),
tarai(y - 1, z, x),
tarai(z - 1, x, y)
)
end
private :tarai
end
make_tarai
tarai(100, 50, 0)
トップレベルで make_tarai を定義すると、定義式の中の self は main になります。define_method は Module クラスのメソッドなので、一般的には module ... end か class ... end の中でしか使えないのですが、main には同名のシングルトン・メソッドが定義されていて、実行すると、Object クラスにメソッドが登録されます。
ここでは、トップクラスでメソッドを定義したときのように、private にしました。
ただ、メソッドにしてもほとんど速度は変わりません。Proc にしろ、メソッドにしろ、環境を背負っている分、遅いのでしょうか。
そこで、この辺りでクロージャに見切りをつけ、cache をインスタンス変数で持つ方法を試してみます。
メモをインスタンス変数に格納する
def make_cache(arity)
seed = "{}"
(arity - 1).times do
seed = "Hash.new { |hash, key| hash[key] = #{seed} }"
end
eval(seed)
end
class Tarai
def initialize
@cache = make_cache(3)
end
def call(x, y, z)
return y if x <= y
@cache[x][y][z] ||= call(
call(x - 1, y, z),
call(y - 1, z, x),
call(z - 1, x, y)
)
end
end
tarai = Tarai.new
tarai.call(100, 50, 0)
ついに、0.007 秒の世界に突入しました。
ぶっちぎりの速さです。
関数型言語に惑わされてなのか、メモ化というとすぐにクロージャだと思い込んでいましたが、Purely Object-Oriented Programming Language である Ruby の場合、素直にオブジェクトを使えばよかったんですね。
まとめ
Ruby でメソッドをメモ化する時には、クロージャではなく、普通にインスタンスを作って、インスタンス変数にメモを格納する。
引数が複数あるときは、配列にして Hash オブジェクトのキーにするのではなく、引数の数だけ多重 Hash にする。