1

数日前、巨大なグラフ (ほぼ​​ 100 万の頂点と 600 万のエッジ) でKosaraju のアルゴリズムを実行しているときに問題が発生しました。問題は、アルゴリズムのDFS (Depth First Search)部分にありました。これは再帰的です -スタック レベルが深すぎます。アルゴリズムを Ruby で実装しました。使用した Ruby のバージョンは 1.9.3 でした。

スタック サイズを確認するために、簡単な手順を実行することにしました。

def r n
  p n
  r n+1
end

r 1

終了前のスタックサイズを示します。使った

ulimit -a

スタックサイズを確認するコマンドと

ulimit -s 32768     # Seems like this is the maximum stack size for mac OS
ulimit -s unlimited # => Invalid argument error

スタックサイズを変更します。スタックサイズを変更した後でも、r-procedure は同じ番号 - 8193 を示しました。Ruby を 1.8.7 に変更した後、最後の番号は 19177 になりました。

最終的に、Ubuntu を使用している友人を見つけました。スタック サイズは無制限です。Kosaraju のアルゴリズムを正常に実行しました。

どうすればMacでできますか？

4

2 に答える 2

0

スタックサイズの制限を変更するための正しい構文は次のとおりです。

ulimit -S -s 32768

OS X 10.7.3ではulimit -S -s unlimited、制限が65532に設定されます。

于 2012-04-15T13:30:31.967 に答える
0

OS X の値に加えて、Ruby プログラムのスタック サイズは、環境変数、、およびulimitで制御できます。irb セッションでデフォルト値を確認できます。RUBY_THREAD_VM_STACK_SIZERUBY_THREAD_MACHINE_STACK_SIZERUBY_FIBER_VM_STACK_SIZERUBY_FIBER_MACHINE_STACK_SIZE

RubyVM::DEFAULT_PARAMS
=> {:thread_vm_stack_size=>1048576,
    :thread_machine_stack_size=>1048576,
    :fiber_vm_stack_size=>131072,
    :fiber_machine_stack_size=>524288}

たとえば、VM スタック サイズを 2097152 に変更する場合は、次のようにします。

RUBY_THREAD_VM_STACK_SIZE=2097152 ruby script.rb

しかし、この特定のケースでは、Ruby でまったく同じアルゴリズムを実装していて、同じ問題があり、スタック サイズを増やすだけでは十分ではありませんでした。私にとってうまくいった解決策は、再帰なしでアルゴリズムを実装することでした。

于 2015-02-23T16:53:27.597 に答える