竹内関数をメモ化で高速化する工程 (Python には負けたくない)


はじめに

Ruby で竹内関数をメモ化によって、高速にしようとあれこれやります。


竹内関数とは

これです。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) のように引数がひとつの時には、特に問題はありません。


Ruby

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)


すればOKです。

ここでは、計算結果を、引数をキーにした Hash オブジェクト cache にメモしています。ちなみに、cache をグローバル変数にしたくないので、lambda を使ってクロージャを作っています。

def ... end で囲まれた空間は、局所変数の独立した 名前空間 を作るので、def で作ったメソッドは外側の局所変数をキャプチャーできず、クロージャにはなりません。

その代わり、lambda 等を使ってクロージャを作る時には、def ... end の中は、局所変数に関してはクリーンルームになるので、クロージャを返すメソッドを作った上で、クロージャを作るのがオススメのはずです。多分。

話が飛んでしまいましたが、Fibonacci の場合と違い、竹内関数の場合、引数が3つあります。これをどう Hash オブジェクトに登録するかです。


Python ならどうするか

Python なら、当然引数を tuple にして、dict オブジェクトに登録するはずです。

まずは、クロージャを使って、


Python

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 のデフォルト引数は関数を定義した時に一度だけ評価されるので、


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)


でもOKでしょう。tarai 関数を何度実行しても、常に同じ dict オブジェクトが使われるので、一度計算結果をメモしてしまえば、次に tarai を実行した時にもそのメモが使えます。

手元で計算すると、tarai(100, 50, 0) で約0.03 秒程度です。


Ruby で同じようなことをすると

Rubyの場合、デフォルト引数はメソッドを実行するたびに評価されるので、Python と違い、メソッドを実行するたびに一からメモを取り直すことになってしまいます。

どちらがいいのか私にはよく分かりません。Python が変わっているような印象ですが、どちらが勝ちで、どちらが負けという話でないことは間違いなさそうです。

そういうわけで、Ruby の場所、クロージャでいきます。

Ruby には tuple がないので、配列でやるしかありません。


Ruby

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 秒前後かかってしまいました。完敗です。


Ruby

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 に代入することができます。

そうすると、こんな感じになります。


Ruby

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 が勝ったとはいえ、


Ruby

    cache_y = cache_x[x] ||= {}

cache_z = cache_y[y] ||= {}
cache_z[z] ||= tarai.call(...

の部分がまだだるいです。どうせなら cache[x][y][z] ||= tarai.call( ... としたいです。


Hash のデフォルト値を使う

Ruby の場合、


Ruby

cache = Hash.new { |hash, key| hash[key] = {} }


とすることで、未登録のキーに出くわしたとき、新たな Hash オブジェクトを作って、そのキーに登録するような Hash オブジェクトを作ることができます。

これを多重にすればいいわけです。


Ruby

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)


これでOKです。

とはいえ、この cache の定義もだるいです。何とかスマートにしたいものです。

そこで、cache の右辺をよく見ると、ラスボス的な {}Hash.new { |hash, key| hash[key] = ... } でラップしていけば良さそうだと分かります。メタプログラミングで何とかしましょう。


メタプログラミング登場

方針としては、何重にもなった Hash.new {} の文字列を作って、eval することにします。

引数の数が3つの場合、{} を2回 Hash.new {} でラップすればいいから、メモ化する際の引数の数を arity とすると、


Ruby

def make_cache(arity)

seed = "{}"
(arity - 1).times do
seed = "Hash.new { |hash, key| hash[key] = #{seed} }"
end
eval(seed)
end

この make_cache があれば、簡単に多重 Hash を作ることができます。


Ruby

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 の登場です。


Ruby

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 を定義すると、定義式の中の selfmain になります。define_method は Module クラスのメソッドなので、一般的には module ... endclass ... end の中でしか使えないのですが、main には同名のシングルトン・メソッドが定義されていて、実行すると、Object クラスにメソッドが登録されます。

ここでは、トップクラスでメソッドを定義したときのように、private にしました。

ただ、メソッドにしてもほとんど速度は変わりません。Proc にしろ、メソッドにしろ、環境を背負っている分、遅いのでしょうか。

そこで、この辺りでクロージャに見切りをつけ、cache をインスタンス変数で持つ方法を試してみます。


メモをインスタンス変数に格納する


Ruby

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 にする。