5

私はこのルビーコードを持っています:

def get_sum n
    return 0 if n<1
  (n%3==0 || n%5==0) ? n+get_sum(n-1) : get_sum(n-1) #continue execution
end 

puts get_sum 999

までの値で機能しているようです999。試し9999てみると、次のようになります。

stack level too deep (SystemStackError)

だから、私はこれを追加しました：

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

しかし、何も起こりませんでした。

私のルビーバージョンは次のとおりです。

ruby 1.9.3p392 (2013-02-22 revision 39386) [x86_64-darwin12.2.1]

また、マシンのスタック サイズulimit -s 32768を増やしましたが、これは 32MB だと思います。

小さい数で動作するので、コードのせいではないと思います9999。大きな数ではないと思います。RAMは8GBありますが、十分だと思います。アイデア/ヘルプはありますか？

4

2 に答える 2

4

問題は、ルーチンがあることですn+get_sum(n-1)。n の公約数が 3 または 5 の場合、Ruby はこのルーチンに進みます。これは末尾再帰では最適化できません。Ruby は、現在のフレームを保持して現在のフレームを保持する必要があり、計算さnれたときにのみ、get_sum(n-1)Ruby はフレームに戻って破棄できます。

一般に、スタック領域は高価です。オペレーティング システムは、プロセスごとに約 2M (おそらくそれ以上) のスタック スペースを予約します。これはすぐに消費できます。あなたのコードでは、(9999/3 + 9999/5)再帰呼び出しがすべてのスタック スペースを消費しました。

再帰的なプログラミング パターンを維持したい場合は、メソッド呼び出しの動作を再帰的 (現在の状態) から反復的に変更する必要があります。

def get_sum(n, sum = 0)
  return sum if n < 1
  if n % 3 == 0 || n % 5 == 0
    get_sum(n - 1, sum + n)
  else
    get_sum(n - 1, sum)
  end
end

ただし、Ruby の末尾再帰の最適化はそれほど強力ではないようです。上記のコード サンプルには、2 つの異なるget_sum()テール コールがあります。Ruby はこれを最適化しません。2 つの呼び出しを 1 つに書き直す必要があります。

さらに、提供した微調整でこれを機能させるにはRubyVM、実行時にメソッド定義をロードする必要があります。これは、RubyVM微調整が実行時に行われるためです。メソッド定義を同じファイルに直接配置することはできません。そうしないと、コンパイル時にメソッドが解析され、最適化が有効になりません。

get_sum微調整後に別のファイルとrequireそのライブラリに入れることができますRubyVM：

# file: test_lib.rb
def get_sum(n, sum = 0)
  if n < 1
    sum
  else
    get_sum(n - 1, sum + (n % 3 == 0 || n % 5 == 0 ? n : 0))
  end
end
# eof

# file: test.rb
RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false
}

require_relative 'test_lib'

puts get_sum(999999)

または、eval実行時に String 内のメソッド定義を評価するために使用します。

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

eval <<END
  def get_sum(n, sum = 0)
    if n < 1
      sum
    else
      get_sum(n - 1, sum + (n % 3 == 0 || n % 5 == 0 ? n : 0))
    end
  end
END

puts get_sum(990000)
于 2013-04-03T13:35:10.103 に答える