Ruby で遅延評価
>ところで、このように書けば一般に(メモ化つきの)遅延評価オブジェクトというのを書くことができる。
>
>class Lazy
def initialize(&b)
@value = nil
@block = b
end
def force
@value = @block.call() if @value.nil?
@value
end
end
tak(100, 50, 0) = 100
ruby ./lazy.rb 100 50 0 1.02s user 0.04s system 98% cpu 1.065 total > >とても遅い。 Proc オブジェクトを作るのは重いからだろう。そこで、ちょっと tak を書換える。どうせ tak を呼ぶと x と y はすぐに force してしまうので、 Lazy にしなくても差し支えないとみなす。 > >def tak(x, y, z)
if x.force <= y.force
y.force
else
tak(tak(x.force-1, y, z),
tak(y.force-1, z, x),
Lazy.new {tak(z.force-1, x, y)})
end
end > >こうすると凄く速くなった。 > >% time ruby ./lazy.rb 100 50 0
tak(100, 50, 0) = 100
ruby ./lazy.rb 100 50 0 0.21 user 0.02s system 94% cpu 0.250 total > >ふつうにテーブルに書き出すより速い。これは、「後で使うかもしれないもの」をすべてテーブルに登録しているのと、本当に必要になったものだけをメモ化しているのの差と言えるのかも。 > >Scheme でもたらいまわし関数でも同じよーな方法は使えて、確かに少し速くなるけどここまで劇的な差はありません。 Ruby の Proc はそんなにコストがかかるんだなぁ。 OCaml は型の問題があるので面倒なため、やっていません。 >
def initialize(&b)
@value = nil
@block = b
end
def force
@value = @block.call() if @value.nil?
@value
end
end
class Object
def force; self; end
end
def tak(x, y, z)
if x.force <= y.force
y.force
else
tak(Lazy.new {tak(x.force-1, y, z)},
Lazy.new {tak(y.force-1, z, x)},
Lazy.new {tak(z.force-1, x, y)})
end
end
>
tak(100, 50, 0) = 100
ruby ./lazy.rb 100 50 0 1.02s user 0.04s system 98% cpu 1.065 total > >とても遅い。 Proc オブジェクトを作るのは重いからだろう。そこで、ちょっと tak を書換える。どうせ tak を呼ぶと x と y はすぐに force してしまうので、 Lazy にしなくても差し支えないとみなす。 > >def tak(x, y, z)
if x.force <= y.force
y.force
else
tak(tak(x.force-1, y, z),
tak(y.force-1, z, x),
Lazy.new {tak(z.force-1, x, y)})
end
end > >こうすると凄く速くなった。 > >% time ruby ./lazy.rb 100 50 0
tak(100, 50, 0) = 100
ruby ./lazy.rb 100 50 0 0.21 user 0.02s system 94% cpu 0.250 total > >ふつうにテーブルに書き出すより速い。これは、「後で使うかもしれないもの」をすべてテーブルに登録しているのと、本当に必要になったものだけをメモ化しているのの差と言えるのかも。 > >Scheme でもたらいまわし関数でも同じよーな方法は使えて、確かに少し速くなるけどここまで劇的な差はありません。 Ruby の Proc はそんなにコストがかかるんだなぁ。 OCaml は型の問題があるので面倒なため、やっていません。 >
ここでの遅延評価による高速化にメモ化は関係ありません。結果の値に寄与しない引数 z を評価せずに済ませることができるからです。