ruby-list

立石です．

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>

Thread

Prev Next

In This Thread

Prev Next

[#35685] Exerb 2.0.0 動きません — AOKI Yoshihiro <aoki@...>

[#35688] サブクラスのオブジェクト生成時に、スーパークラスの初期化を行うには ? — Onodera Takafumi <onodera-tak@...>

[#35690] Ruby/SDL がうまく動きません — Mitsuhiko_Tomomi <mikkun_ota@...>

[#35713] Selection IPv4/IPv6 at TCPSocket — NISHI Takao <zophos@...9.com>

[#35715] すべてのメソッドを（最小コストで）フックしたい — "井上 浩一" <kyoui32@...>

[#35716] すべてのメソッドを最小コストでフックしたい。 — "井上 浩一" <kyoui32@...>

[#35718] Re: すべてのメソッドを最小コストでフックしたい。 — "井上 浩一" <kyoui32@...>

[#35722] パターンマッチした値を保持する変数は — goto@...

[#35729] SMTP サーバクラス — とみたまさひろ <tommy@...>

[#35730] how to share some value through parent class's method — YANAGAWA Kazuhisa <kjana@...4lab.to>

[#35733] tail recursion elimination — Takaaki Tateishi <ttate@...>

[#35737] Win32 環境での PStore の動かし方 — fukumit <fukumit@...>

[#35743] FortranArray, yet another handler of array — NISHIMATSU Takeshi <t-nissie@...>

[#35745] Ruby vs. Expect — T_A_K_E <koichi.takehara@...>

[#35748] DBD::OCI8 based on Ruby/OCI8 — KUBO Takehiro <kubo@...>

[#35754] [ANN] SWIG 1.3.14 リリース — Shibukawa Yoshiki <yoshiki@...>

[#35759] Bignum fast multiplication — IKEGAMI Daisuke <daisu-ik@...>

[#35769] [ANN] SWIG-Ruby ドキュメント翻訳 — Shibukawa Yoshiki <yoshiki@...>

[#35770] cgi.rb の form — rio-t@...

[#35772] Unsecure world writeable dirの警告 — "井上 浩一" <kyoui32@...>

[#35789] multipart な CGI を速くしたい — Takashi Kanai <kanai@...4u.or.jp>

[#35792] "self = / ー /" でエラー — "Tatsuaki Nagai" <Tatsuaki_Nagai@...>

[#35795] Re: "self = / ー /" でエラー — "Tatsuaki Nagai" <Tatsuaki_Nagai@...>

[#35799] Re: "self = / ー /" でエラー — "Tatsuaki Nagai" <Tatsuaki_Nagai@...>

[#35810] [ANN] RubyCocoa 0.2.7 — FUJIMOTO Hisakuni <hisa@...>

[#35811] 祝 1.7.3 But cast_256.so Segmentaation fault — "Inoue" <rubyist@...1.117.ne.jp>

[#35813] — NAWATE Masahiko <agul@...>

[#35816] [ANN] irbsh-0.8.0 — rubikitch <rubikitch@...>

[#35817] CGI::pretty — rio-t@...

[#35821] [ANN] RDE0.9.7.0 — sakazuki <QZS01353@...>

[#35822] profile.rb の使い方 — rio-t@...

[#35823] [Q]UNIX command in Ruby — Masaaki Sakano <mas@...>

[#35829] cygwin 版 ruby で ARGV に日本語 — rio-t@...

[ruby-list:35733] tail recursion elimination

Thread

In This Thread

[#35715] すべてのメソッドを（最小コストで）フックしたい — "井上浩一" <kyoui32@...>

[#35716] すべてのメソッドを最小コストでフックしたい。 — "井上浩一" <kyoui32@...>

[#35718] Re: すべてのメソッドを最小コストでフックしたい。 — "井上浩一" <kyoui32@...>

[#35772] Unsecure world writeable dirの警告 — "井上浩一" <kyoui32@...>