たらいまわし関数

Ruby 30分プログラム

30分プログラム、その184。Rubyでたらいまわし。

輪講の準備でメモ化(memoization)を調べてたら、たらい回し関数のことを思い出したので書いてみる。
曰く、遅延評価だと早くなる関数らしく、Haskellってすげーという文脈でよく登場する。

普通に計算するやつと遅延評価するやつと、メモ化するやつをつくってみた。

使い方

irb> tak 10,5,0
10

irb> tak 12,6,0
12

なお速度は、

# 普通のやつ
$ ruby 184-tarai.rb
10
ruby 184-tarai.rb  1.51s user 0.12s system 77% cpu 2.107 total

# 遅延評価するやつ
$ time ruby 184-tarai_lazy.rb
10
ruby 184-tarai_lazy.rb  0.26s user 0.08s system 76% cpu 0.449 total

# メモ化するやつ
$ time ruby 184-tarai_memo.rb
10
ruby 184-tarai_memo.rb  0.26s user 0.08s system 75% cpu 0.444 total

ソースコード

#! /opt/local/bin/ruby -w
# -*- mode:ruby; coding:utf-8 -*-
#
# 184-tarai.rb -
#
# Copyright(C) 2007 by mzp
# Author: MIZUNO Hiroki
# http://mzp.sakura.ne.jp/
#
# Timestamp: 2007/11/17 22:01:53
#
# This program is free software; you can redistribute it and/or
# modify it under the same terms as Ruby itself.
#

# 普通のやつ
def tak(x,y,z)
  if x <= y then
    y
  else
    tak(tak(x-1,y,z),tak(y-1,z,x),tak(z-1,x,y))
  end
end

# 遅延評価をするバージョン
def lazy(&x)
  memo = nil
  lambda {
    if memo == nil then
      memo = x.call
    end
    memo
  }
end

def force(x)
  x.call
end

def tak_lazy(x,y,z)
  if force(x) <= force(y) then
    y
  else
    tak_lazy(tak_lazy(lazy{ force(x) - 1},y,z),
             tak_lazy(lazy{ force(y) - 1},z,x),
             tak_lazy(lazy{ force(z) - 1},z,x))
  end
end

# 一度やった計算を記憶するやつ(memoization)
$table = {}
def tak_memo(x,y,z)
  if $table.key? [x,y,z] then
    $table[[x,y,z]]
  else
    $table[[x,y,z]] = if x <= y then
                        y
                      else
                        tak_memo(tak_memo(x-1,y,z),
                                 tak_memo(y-1,z,x),
                                 tak_memo(z-1,x,y))
                      end
  end
end

puts tak(10,5,0)
puts force(tak_lazy(lazy{10},lazy{5},lazy{0}))
puts tak_memo(10,5,0)

参考