1

几天前，我在一个巨大的图（几乎一百万个顶点和六百万条边）上运行Kosaraju 的算法时遇到了一个问题。问题出在算法的DFS（深度优先搜索）部分，即递归堆栈级别太深。我在 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.3ulimit -S -s unlimited上，将限制设置为 65532。

于 2012-04-15T13:30:31.967 回答
0

除了 OS X值之外，ulimitRuby 程序中的堆栈大小还可以通过以下环境变量来控制：RUBY_THREAD_VM_STACK_SIZE、RUBY_THREAD_MACHINE_STACK_SIZE和. 您可以检查 irb 会话中的默认值：RUBY_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 回答