Исключение переполнения стека при вероятностном расчете

Question

Я делал проблему 14 в Project Euler (примечание: я не ищу решение проблемы 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.StackruError soe) {
                exceptionCount++;
                System.err.println(soe + "\n");
            }
        }
        System.out.println("Exception count: " + exceptionCount);
    }
}

Я также хотел предоставить полный вывод, но это ставит меня за пределы персонажа.

Answer 1

Ваша рекурсия слишком глубока. Вы можете увеличить стек вызовов на вашей JVM с -Xss 4096m, но это грубая сила. Будьте более элегантными и используйте 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;
    }

Answer 2

В вашем исключении stackru вы увидите причину исключения. В этом случае это слишком много рекурсии, и вы увидите это по повторяющимся кадрам стека в трассировке стека.

Попробуйте сделать ваш алгоритм итеративным, а не рекурсивным, и ваша проблема решена.