2014-01-20 67 views
1

當我遇到一個有趣的堆棧溢出異常時,我在做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); 
    } 
} 

我想提供完整的輸出爲好,但使我在字符的限制。

+1

使用while循環而不是遞歸在'getChainLength()' - 這應該加快了一點東西和免費頗多堆棧。 – tucuxi

回答

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; 
    } 
1

你會在你的stackoverflow異常中看到異常的原因。在這種情況下,它的遞歸太多了,你會通過堆棧跟蹤中的重複棧幀來看到它。

試着讓你的算法迭代而不是遞歸,你的問題就解決了。