我在项目欧拉(Euler)上做问题14(注意:我不是在寻找欧拉(Euler)问题的解决方案),当我遇到一个有趣的堆栈溢出异常时。
我的非稳态方法效果很好,但是当我尝试使用概率方法遇到同样的问题时,我会遇到堆栈溢出异常。有趣的是,例外仅发生大约17%的时间。一千个跑步产生了166个例外。
我知道我的概率逻辑存在缺陷,但是我对防止它们发生的例外和方法更感兴趣。我是否只需要进行一些内存管理,也许在使用后将一些变量设置为无效?如果是这样,关键点在哪里?
代码如下:
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);
}
}
我也想提供完整的输出,但这使我超过了角色限制。
您的递归太深。您可以使用-Xss 4096m
增加JVM上的通话堆栈,但这是蛮力。更优雅,使用while
循环代替getChainLength()
中的递归:
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;
}
您将在stackoverflow异常中看到异常的原因。在这种情况下,它太多了递归,您会通过堆栈中的重复堆叠式框架看到它。
尝试使您的算法迭代而不是递归,并解决了问题。