CRubyで末尾最適化を使った再帰

ruby

Schemeなんかと違って、言語としてのRubyは末尾最適化（Tail Call Optimization）の実装は必須ではないけど、処理系としてのCRubyは2.0.0からオプション扱いで入っている、という話。2012年の6月ごろにはMatzさんはTCOをデフォルトにするという考えもあったようだけど、ここにある議論によれば、Ruby 2.0系のマイナーバージョンまで先延ばしになった模様。性急にTCOを入れなかった理由は、

  • バックトレースを失うので一般的なRuby利用者に影響が大きい
  • set_trace_func()のサポートが大変
  • 文法。ちゃんとドキュメントに落としこむのが難しい。これは半分冗談、半分本気

ということらしい。JRubyでも、JVMがサポートしない限り実装が難しいという（あれ？ Clojureは明示的な末尾呼び出しの最適化をやってるように思うけど）。

Rubyはイテレータでeachもmapもfoldもあるので、forを使わないのと同じくらい再帰を使う場面がないように思う。リスト処理という意味でいえば、RubyのイテレータはTCO入りの再帰と言える気がする。トランポリン的な相互再帰とかでもない限り、これで困らない。と、思うのはSchemerじゃないからなのか。

でも、例えば、Euler Project 160なんかは再帰を使ったほうがスンナリ書けて、しかも、TCOがないとスタックがあっという間に溢れるような問題だ。問題は、

For any N, let f(N) be the last five digits before the trailing zeroes in N!.
For example,

9! = 362880 so f(9)=36288
10! = 3628800 so f(10)=36288
20! = 2432902008176640000 so f(20)=17664

Find f(1,000,000,000,000)

という感じ。これを次のように書いた。

def f(n, res)
  if n == 1
    return res
  end

  res = res * n
  res = res.to_s.sub(/0+$/, '')
  res = res[-5..-1] if res.size > 5

  res = res.to_i
  f(n - 1, res)
end

p f(100, 1)
#p f(1_000_000_000_000, 1)

ぼくの環境ではnが1000ではオッケーで、10000にするとスタックは溢れた。Ruby 1.9.3-p286ではなく、Ruby 2.0.0系のheadを使って以下のように書いた。RubyVMでTCOをオンにできる。ついでに文字列と数字の変換が遅いので、全部数値としてやるように変更。

RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false
}

RubyVM::InstructionSequence.new(<<-EOF).eval
def f(n, res)
  if n == 1
    return res
  end

  res = res * n
  while (res % 10) == 0
    res /= 10
  end

  res %= 100000

  f(n - 1, res)
end

 p f(1_000_000_00, 1) # 18 sec
# p f(1_000_000_000_000, 1)
EOF

$ time ruby -v p160tco.rb
ruby 2.0.0dev (2012-10-12 trunk 37163) [x86_64-darwin11.4.2]
23616
ruby -v p160tco.rb  17.73s user 0.04s system 94% cpu 18.731 total

設問より4桁少なくして18秒ということは、答えがでるのに18万秒かかるということで、これは丸二日以上かかる計算。無理。メソッド呼び出しをやめて素直にfor的な何かを使うと、もしかしたら速くなるかな。

ともあれ、いくらループを回してもスタックは溢れなくなった。