6

我为课堂作业编写了一个简单的方法，该方法使用递归（是的，它必须使用递归）来计算分形图案中的三角形数量：

public static BigInteger triangleFract(int layer) {
    if(layer < 0) {
        throw new IllegalArgumentException("Input must be >= 0");
    } else if(layer == 0) {
        return new BigInteger("0");
    } else if (layer == 1) {
        return new BigInteger("1");
    } else {
        return triangleFract(layer - 1)
              .multiply(new BigInteger("3"))
              .add(new BigInteger("2"));
    }
}

我一直在尝试做的是了解 int 层可以有多大，以限制用户输入。经过一些测试后，我在 6700+ 左右得到了堆栈溢出，这很好。

令我困扰的是，如果层数以千计，该方法通常会运行，但它仍然可以随机遇到一个StackOverflowError.

例如，我选择将层限制为 4444，它似乎几乎总是能够处理它，但每隔一段时间它似乎仍然会溢出。

为什么这样做？我能做些什么吗？

4

6 回答 6

3

也许 JVM 已经确定（通过逃逸分析）BigInteger 可以分配在堆栈上而不是堆上。根据实现此优化的时间，所需的堆栈大小会有所不同。

也就是说，可能还有许多其他原因，并且行为可能取决于您使用的 JVM。

于 2012-11-17T14:46:50.917 回答
2

考虑转移到迭代版本。我认为，如果您开发递归算法，则必须控制级别深度或根本不使用递归。

于 2012-11-17T13:40:48.173 回答
0

我无法重现您的“波动”效果。这是非常确定的代码，因此您每次都应该得到相同的结果（包括堆栈溢出错误）。

你是怎么测试的？您是否为 4444 测试的每次尝试都运行了一个新的 jvm？（或者它只是在循环中调用的 triangleFrac(4444); ？）。

你的操作系统是什么，java版本等...

我问是因为我真的不喜欢像这样未解决的问题 --- 这样的事情可能会在哪里（和何时）咬你；）。

哦...顺便说一句，无论如何，您应该使用 BigInteger 中的 ONE 和 ZERO 常量（并为 2 和 3 创建自己的常量。这应该可以为您节省相当多的内存（是的，我知道，这不是你的问题）。

于 2012-11-17T16:30:43.643 回答
0

对于那些无法重现这种波动的人。查找layer从哪个方法将可靠地抛出的值StackOverflowError。该值越接近实际阈值越好。现在从循环内部（在我的机器上maxLayer = 11500）调用此方法：

int i = 11500;
while (true) {
    System.out.println(i);
    triangleFract(i++);
}

它会抛出StackOverflowError. 现在稍微降低这个值（看起来 5-10% 应该足够了）：

int i = 10500;
while (true) {
    System.out.println(i);
    triangleFract(i++);
}

好吧，在我的机器上，这不会引发任何错误并成功跳过11500。实际上它工作正常，直到16000.

因此，无论它是什么，它都可能涉及 JVM 优化。我试图用 -XX:+PrintCompilation. 我看到了 JIT 在循环时是如何工作的：

117   1       java.lang.String::hashCode (64 bytes)
183   2       java.lang.String::charAt (33 bytes)
189   3       sun.nio.cs.UTF_8$Decoder::decodeArrayLoop (553 bytes)
201   4       java.math.BigInteger::mulAdd (81 bytes)
205   5       java.math.BigInteger::multiplyToLen (219 bytes)
211   6       java.math.BigInteger::addOne (77 bytes)
215   7       java.math.BigInteger::squareToLen (172 bytes)
219   8       java.math.BigInteger::primitiveLeftShift (79 bytes)
224   9       java.math.BigInteger::montReduce (99 bytes)
244  10       sun.security.provider.SHA::implCompress (491 bytes)
280  11       sun.nio.cs.UTF_8$Encoder::encodeArrayLoop (490 bytes)
282  12       java.lang.String::equals (88 bytes) 11400
289  13       java.lang.String::indexOf (151 bytes)
293  14       java.io.UnixFileSystem::normalize (75 bytes)
298  15       java.lang.Object::<init> (1 bytes)
298  16       java.util.jar.Manifest$FastInputStream::readLine (167 bytes)
299  17       java.lang.CharacterDataLatin1::getProperties (11 bytes)
300  18       NormalState::triangleFract (74 bytes)
308  19       java.math.BigInteger::add (178 bytes)
336  20       java.lang.String::lastIndexOf (151 bytes)
337  21       java.lang.Number::<init> (5 bytes)
338  22       java.lang.Character::digit (6 bytes)
340  23       java.lang.Character::digit (168 bytes)
342  24       java.lang.CharacterDataLatin1::digit (85 bytes)
343  25       java.math.BigInteger::trustedStripLeadingZeroInts (37 bytes)
357  26       java.lang.String::substring (83 bytes)
360  27       java.lang.String::lastIndexOf (10 bytes)
360  28       java.lang.String::lastIndexOf (29 bytes)
361  29       java.math.BigInteger::<init> (24 bytes)
361  30       java.lang.Integer::parseInt (269 bytes)
361  31       java.math.BigInteger::<init> (8 bytes)
362  32       java.math.BigInteger::<init> (347 bytes)
404  33       java.math.BigInteger::multiply (72 bytes)
404  34       java.math.BigInteger::add (123 bytes)

可以编译吗？让我们尝试延迟编译，以便它尽可能晚地影响我们。我尝试使用-XX:CompileThresholdflag 并很快找到一个值 ( -XX:CompileThreshold=1000000)，它不会让我的循环跳过11500。

更新

我终于在没有调整编译阈值的情况下复制了它。对我来说，它看起来只有在我的 IDE（IntelliJ IDEA）中运行程序时才会发生。所以这可能与IDEA的启动器有关。我复制了它的命令行并在一个小脚本中使用它：

for I in `seq 1 100`; do 
        java ... com.intellij.rt.execution.application.AppMain \
        Triangle 2>&1| grep Stack; done | wc -l

我发现它通常会打印出少于 100 (95-98) 的内容。这与我手动操作时看到的一致。当我跳过启动器时：

for I in `seq 1 100`; do 
        java \
        Triangle 2>&1| grep Stack; done | wc -l

它总是打印出 100。

于 2012-11-17T20:05:50.877 回答
0

实际上您可以做一些事情：增加最大堆栈大小。这是在 JVM 启动时使用如下选项完成的-Xss：

java -Xss40m MainClass

注意不要设置过高的值。如果您必须超过 60M - 70M，则建议重新设计您的代码。

于 2012-11-17T15:12:50.940 回答
0

允许递归到那个深度是一种设计味道。

试试这个迭代版本：

public static BigInteger triangleFract(int layer) {
    if (layer < 0) {
        throw new IllegalArgumentException("Input must be >= 0");
    }
    if (layer == 0) {
        return BigInteger.ZERO;
    }
    BigInteger result = BigInteger.ONE;
    BigInteger two = new BigInteger("2");
    BigInteger three = new BigInteger("3");
    for (int i = 1; i < layer; i++) {
        result = result.multiply(three).add(two);
    }
    return result;
}

笔记：

  • 使用BigInteger.ZEROandBigInteger.ONE而不是为这些值创建新实例
  • 删除了多余的else-终止语句之后没有（例如）elsereturn
  • 每次迭代都重用new BigInteger("2")而new BigInteger("3")不是创建新实例
于 2012-11-17T13:56:47.533 回答