竹内関数をRubyとGaucheで

Lispは遅くて実用にならないと揶揄されるで、それに論駁するために竹内郁雄先生が2時間ほどで考えだしたという「たらい回し関数」を、手元で実行してみた。計算量はtarai(2n,n,0)の場合にO(n^n)ということらしい。これだけ短いコードで、これほどの計算量の爆発感がある関数は、ほかにないのじゃないかという。

def tarai(x, y, z)
  if y < x then
    tarai( 
          tarai(x-1, y, z),
          tarai(y-1, z, x),
          tarai(z-1, x, y)
          )
  else
    y          # not z!
  end
end

loop do
  print "x, y, z? :"
  print tarai(*(gets.chomp!.split(" ").map(&:to_i))), "\n"
end

12,6,0あたりでも2秒ほどかかる。14,7,0とすると、もう返事が戻ってこないぐらい時間がかかる。

計算量が多いといっても重複が多いので、memoizeすると一気に速くなる。Rubyのmemoizeの定型句は「||=」がキモらしい。

@tarai = {}

def tarai(x, y, z)
  @tarai[[x, y, z]] ||= 
  if y < x then
    tarai( 
          tarai(x-1, y, z),
          tarai(y-1, z, x),
          tarai(z-1, x, y)
          )
  else
    y          # not z!
  end
end

これで100程度なら一瞬で返事が戻ってくるようになった。

Gaucheでやってみた。そういえばSnow Leopardでは、MacPortsでGaucheがうまくインストールできない状態のようで、依存しているライブラリを32/64bit両対応のuniversalな感じにしてインストールしなおす必要があった。それにしてもぜんぜん動かなくて怒られまくると思ったら、defineじゃなくてdefunと書いていた。こんな些細なことでLispやSchemeにはどうしてバリエーションがあるのだろうか。

(define (tarai x y z)
  (if (not (< y x))
      y
      (tarai
       (tarai (- x 1) y z)
       (tarai (- y 1) z x)
       (tarai (- z 1) x y))))

(define (main args)
  (let ((n (string->number (car (cdr args)))))
    (tarai (* n 2) n 0)))

% time gosh tak.scm 6
gosh tak.scm 6  0.84s user 0.00s system 96% cpu 0.881 total
% time gosh tak.scm 7
gosh tak.scm 7  39.23s user 0.06s system 98% cpu 39.764 total

なるほど、全然速くない。あれ。