11

这是我的程序的上下文。

一个函数有 50% 的机会什么都不做，有 50% 的机会调用自己两次。程序完成的概率是多少？

我写了这段代码，它显然工作得很好。对每个人来说可能并不明显的答案是这个程序有 100% 的机会完成。但是当我运行这个程序时有一个 StackOverflowError（多么方便；）），发生在 Math.Random() 中。有人可以指出它来自哪里，并告诉我我的代码是否错误？

static int bestDepth =0;
static int numberOfPrograms =0;
@Test
public void testProba(){
   for(int i = 0; i <1000; i++){
       long time = System.currentTimeMillis();
       bestDepth = 0;
       numberOfPrograms = 0;
       loop(0);
       LOGGER.info("Best depth:"+ bestDepth +" in "+(System.currentTimeMillis()-time)+"ms");
   }
}

public boolean loop(int depth){
    numberOfPrograms++;
    if(depth> bestDepth){
        bestDepth = depth;
    }
    if(proba()){
        return true;
    }
    else{
        return loop(depth + 1) && loop(depth + 1);
    }
}

public boolean proba(){
    return Math.random()>0.5;
}

.

java.lang.StackOverflowError
at java.util.Random.nextDouble(Random.java:394)
at java.lang.Math.random(Math.java:695)

. 我怀疑堆栈和其中的函数数量是有限的，但我并没有真正看到这里的问题。

显然欢迎任何建议或线索。

法比安

编辑：感谢您的回答，我用 java -Xss4m 运行它，效果很好。

4

4 回答 4

14

每当调用函数或创建非静态变量时，堆栈都用于为其放置和保留空间。

现在，您似乎正在递归调用该loop函数。这会将参数连同代码段和返回地址一起放入堆栈。这意味着大量信息被放置在堆栈上。

但是，堆栈是有限的。CPU 具有内置机制，可以防止数据被压入堆栈并最终覆盖代码本身（随着堆栈增长）。这称为General Protection Fault. 当发生一般保护故障时，操作系统会通知当前正在运行的任务。因此，起源于Stackoverflow.

这似乎发生在Math.random().

为了解决您的问题，我建议您使用 -Xss 选项来增加堆栈大小Java。

于 2013-08-08T12:22:12.280 回答
4

正如您所说，该loop函数递归调用自身。现在，尾递归调用可以被编译器重写为循环，并且不占用任何堆栈空间（这称为尾调用优化，TCO）。不幸的是，java 编译器不这样做。而且你loop的不是尾递归的。您的选择是：

  1. 正如其他答案所建议的那样，增加堆栈大小。请注意，这只会及时推迟问题：无论您的堆栈有多大，它的大小仍然是有限的。您只需要更长的递归调用链即可突破空间限制。
  2. 用循环重写函数
  3. 使用具有执行 TCO 的编译器 的语言
    1. 您仍然需要将函数重写为尾递归
    2. 或者用蹦床重写它（只需要小改动）。一篇解释蹦床并进一步概括它们的好论文被称为“ Stackless Scala with Free Monads ”。

为了说明 3.2 中的观点，重写后的函数如下所示：

def loop(depth: Int): Trampoline[Boolean] = {
  numberOfPrograms = numberOfPrograms + 1
  if(depth > bestDepth) {
    bestDepth = depth
  }
  if(proba()) done(true)
  else for {
    r1 <- loop(depth + 1)
    r2 <- loop(depth + 1)
  } yield r1 && r2
}

最初的电话是loop(0).run.

于 2013-08-08T12:41:58.373 回答
2

增加堆栈大小是一个很好的临时修复。然而，正如这篇文章所证明的，虽然函数保证最终loop()返回，但所需的平均堆栈深度是无限的。因此，无论您将堆栈增加多少，您的程序最终都会耗尽内存并崩溃。loop()

我们无法肯定地防止这种情况发生；我们总是需要以某种方式在内存中对堆栈进行编码，而且我们永远不会拥有无限的内存。但是，有一种方法可以将您正在使用的内存量减少大约 2 个数量级。这应该使您的程序有更高的返回机会，而不是崩溃。

我们可以通过注意到，在堆栈的每一层，运行程序实际上只需要一条信息：告诉我们是否需要loop()在返回后再次调用。因此，我们可以使用一堆位来模拟递归。每个模拟的堆栈帧只需要一位内存（现在它需要 64-96 倍，具体取决于您是在 32 位还是 64 位中运行）。

代码看起来像这样（虽然我现在没有 Java 编译器，所以我无法测试它）：

static int bestDepth = 0;
static int numLoopCalls = 0;

public void emulateLoop() {
    //Our fake stack.  We'll push a 1 when this point on the stack needs a second call to loop() made yet, a 0 if it doesn't
    BitSet fakeStack = new BitSet();
    long currentDepth = 0;
    numLoopCalls = 0;

    while(currentDepth >= 0)
    {
        numLoopCalls++;

        if(proba()) {
            //"return" from the current function, going up the callstack until we hit a point that we need to "call loop()"" a second time
            fakeStack.clear(currentDepth);
            while(!fakeStack.get(currentDepth))
            {
                currentDepth--;
                if(currentDepth < 0)
                {
                    return;
                }
            }

            //At this point, we've hit a point where loop() needs to be called a second time.
            //Mark it as called, and call it
            fakeStack.clear(currentDepth);
            currentDepth++;
        }
        else {
            //Need to call loop() twice, so we push a 1 and continue the while-loop
            fakeStack.set(currentDepth);
            currentDepth++;
            if(currentDepth > bestDepth)
            {
                bestDepth = currentDepth;
            }
        }
    }
}

这可能会稍微慢一些，但它会使用大约 1/100 的内存。 请注意，BitSet它存储在堆上，因此不再需要增加堆栈大小来运行它。如果有的话，你会想要增加 heap-size。

于 2013-08-09T17:05:38.177 回答
0

递归的缺点是它开始填满你的堆栈，如果你的递归太深，最终会导致堆栈溢出。如果您想确保测试结束，您可以使用以下 Stackoverflow 线程中给出的答案来增加堆栈大小：

如何增加 Java 堆栈大小？

于 2013-08-08T12:21:24.480 回答