概率计算中的堆栈溢出异常

Question

当我遇到一个有趣的堆栈溢出异常时，我在做Project Euler上的问题14（注意：我没有在寻找Project Euler问题的解决方案）。

我的非概率方法工作得很好，但是当我用概率方法尝试同样的问题时，我遇到了堆栈溢出异常。有趣的是，例外只发生在约17％的时间。一千个运行产生了166个例外。

我知道我的概率逻辑是有缺陷的，但我更关心异常的原因以及如何防止它们发生。我是否需要做一些内存管理，也许在使用它们后将一些变量设置为null？如果是的话，关键点在哪里呢？

的代码如下：

public class Problem14_LongestCollatzSequence { 

    private static final int STARTING_CHAIN_LENGTH = 1; 
    private static final int PROBABLY_RIGHT = 100000; 

    /** 
    * Calculate and return the Collatz sequence of a given number. 
    * 
    * @param number The number for which the Collatz sequence is to be 
    * calculated. 
    * @param chainlength The length of the chain for the number. This should 
    * start with an initial value of 1. 
    * @return The Length of the Collatz sequence. 
    */ 
    private static int getChainLength(long number, int chainlength) { 
     // All chains should end with 1. 
     if (number != 1) { 
      // If the number is even, halve the number, otherwise multiply it by 3 and add 1. 
      if (number % 2 == 0) { 
       number = number/2; 
      } else { 
       number = number * 3 + 1; 
      } 
      // Call this function again. 
      return getChainLength(number, ++chainlength); 
     } 
     // Return the length of the chain. 
     return chainlength; 
    } 

    /** 
    * Determine and return the number below a maximum value that will result in 
    * the longest Collatz chain. 
    * 
    * @param maxStartingNumber The maximum value (exclusive) of the numbers 
    * that will be tested. 
    * @return The number that will produce the longest Collatz sequence in the 
    * given range. 
    */ 
    private static int calculateLongestChain(int maxStartingNumber) { 
     Random random = new Random(); 
     int probabilityCounter = 0; 
     int currentChainNumber = 0; 
     int longestChainNumber = 0; 
     int currentChainLength = 0; 
     int longestChainLength = 0; 

     // Get the chain length of random numbers until a certain number of unsuccsessful attempts have been made. 
     while (probabilityCounter <= PROBABLY_RIGHT) { 
      currentChainNumber = random.nextInt(maxStartingNumber); 
      currentChainLength = getChainLength(currentChainNumber, STARTING_CHAIN_LENGTH); 
      // If the current chain-length is bigger than the previously calculated one, reset the counter and update the chain number, otherwise increase the counter. 
      if (currentChainLength > longestChainLength) { 
       probabilityCounter = 0; 
       longestChainLength = currentChainLength; 
       longestChainNumber = currentChainNumber; 
      } else { 
       ++probabilityCounter; 
      } 
     } 
     return longestChainNumber; 
    } 

    private static int calculateLongestChainNP(int maxStartingNumber) { 
     // Non-probabilistic way to calculate the longest Collatz sequence. 
     int currentChainLength = 0; 
     int longestChainLength = 0; 
     int longestChainNumber = 0; 
     // Simply loop through all the numbers in the range to calculate the one resulting in the longest sequence. 
     for (int i = 1; i < maxStartingNumber; i++) { 
      currentChainLength = getChainLength(i, STARTING_CHAIN_LENGTH); 
      if (currentChainLength > longestChainLength) { 
       longestChainLength = currentChainLength; 
       longestChainNumber = i; 
      } 
     } 
     return longestChainNumber; 
    } 

    public static void main(String[] args) { 
     int exceptionCount = 0; 
     for (int count = 0; count < 1000; count++) { 
      try { 
       int testNumber = 1000000; 
       System.out.println("Probabilistic answer: " + calculateLongestChain(testNumber)); 
       System.out.println("Non-probabilistic answer: " + calculateLongestChainNP(testNumber) + "\n"); 
      } catch (java.lang.StackOverflowError soe) { 
       exceptionCount++; 
       System.err.println(soe + "\n"); 
      } 
     } 
     System.out.println("Exception count: " + exceptionCount); 
    } 
} 

我想提供完整的输出为好，但使我在字符的限制。

Answer 1

您的递归太深了。您可以使用-Xss 4096m来增加JVM上的调用堆栈，但这是蛮力。更优雅和getChainLength()使用while循环而不是递归的：

private static int getChainLength(long number, int chainlength) { 
     // All chains should end with 1. 
     while (number != 1) { 
      // If the number is even, halve the number, otherwise multiply it by 3 and add 1. 
      if (number % 2 == 0) { 
       number = number/2; 
      } else { 
       number = number * 3 + 1; 
      } 
      // Call this function again. 
      ++chainlength; 
     } 
     // Return the length of the chain. 
     return chainlength; 
    } 

Answer 2

你会在你的stackoverflow异常中看到异常的原因。在这种情况下，它的递归太多了，你会通过堆栈跟踪中的重复栈帧来看到它。

试着让你的算法迭代而不是递归，你的问题就解决了。