From: Takaaki Tateishi <ttate@...>
Date: 2002-08-10T20:26:56+09:00
Subject: [ruby-list:35733] tail recursion elimination

立石です．

ruby-talkを見ている方には重複してしまいますが，ruby-optimizerという
メソッドの最適化もどきを行う拡張モジュールを紹介させて下さい．

  http://www.ruby-lang.org/en/raa-list.rhtml?name=Optimization+Module

単純に解析木を組換えることでスピードを少し向上させるものです．また末尾
再帰除去も行います．現在いくつか不具合はありますが，だいたいうまく動く
ようです．
簡単な例として，次のような n までの総和を計算する末尾再帰の関数を挙げます．

def sum_(n, acc)
  if( n > 0 )
    return sum_(n-1, acc + n)
  else
    return acc
  end
end
def sum(n)
  sum_(n, 0)
end

def time(str)
  t1 = Time.now
  begin
    yield
  rescue Exception => e
    print("#{str}: #{e.message}\n")
    #print(e.backtrace.join("\n"),"\n")
    return
  end
  t2 = Time.now
  print("#{str}: #{t2 - t1}\n")
end

time("normal"){
  p sum(ARGV[0].to_i)
}
optimize :sum_, :sum
time("optimized"){
  p sum(ARGV[0].to_i)
}

optimize というメソッドによって，この sum_, sum の場合には末尾の
returnと末尾再帰などを排除します．
このスクリプトをsum.rbとして以下のような結果を得ることができました．

環境: linux-2.4.x, Pentium3 1.2GHz, Mem 512MB

$ ruby-1.6 -v
ruby 1.6.7 (2002-08-01) [i686-linux]

$ ruby-1.6 sum.rb 1000
500500
normal: 0.012943
500500
optimized: 0.005142

$ ruby-1.6 sum.rb 3000
normal: stack level too deep
4501500
optimized: 0.008638

$ ruby-1.6 sum.rb 300000
normal: stack level too deep
45000150000
optimized: 1.098245

ループを使うとこんな感じです．

def sum(n)
  acc = 0
  while( n > 0 )
    acc += n
    n -= 1
  end
  acc
end

$ ruby-1.6 sum.rb 300000
45000150000
normal: 0.822583

ループやイテレータには敗けてしまいますね… (^^;
僕は最適化についてはあまり方法を知らないので，案などあれば是非
お願いします．

ついでに，Pythonなどとも比較してみました．Pythonの場合次のスクリ
プトを使いました．

import time
import sys
import string

def sum_(n, acc):
        if n >0:
                return sum_(n-1, acc+n)
        else:
                return acc

def sum(n):
        return sum_(n, 0)

t1 = time.time()
print "sum: " + repr(sum(string.atoi(sys.argv[1])))
t2 = time.time()
print "time: " + repr(t2 - t1)

結果は次の通りで，最適化する前のrubyのメソッドと比べるとpythonの方
が早いです．最適化後には良い勝負になりますが，Pythonの方は9000くら
いまでは再帰できたようです．

$ python 
Python 1.5.2 (#1, Dec 10 2001, 00:15:29)

$ python sum.py 1000
sum: 500500
time: 0.00374591350555

$ python sum.py 3000
sum: 4501500
time: 0.0123699903488

# 他には，sml,mosml,guileなどとも比べてみました．
-- 
Takaaki Tateishi <ttate@kt.jaist.ac.jp>