java - BigInteger 内存泄漏导致 Java 中的堆栈溢出

Question

我正在尝试编写一个优化的斐波那契作为作业，以便能够计算 fib(300) 和 fib(8000)。这是我目前所拥有的( map 是一个 HashMap)。

public static BigInteger fibMemo(int n) {

    if (n <= 1){
        return BigInteger.valueOf(n);
    }

    if (!map.containsKey(n)){
        map.put(n, fibMemo(n-1).add(fibMemo(n-2)));
    }
    return map.get(n);        
}

当我打电话

System.out.println("300: " + FibonacciMemo.fibMemo(300));

就其本身而言，它工作得很好。还有，

System.out.println("8000: " + FibonacciMemo.fibMemo(8000));

如果我注释掉之前对 fib(300) 的调用，则工作正常。但是，如果我保留这两个调用，我会在递归 fibMemo 上出现堆栈溢出。这对我来说似乎很奇怪。有人可以澄清一下情况吗？提前致谢。

代码如下:

import java.util.HashMap; // Import Java's HashMap so we can use it
import java.math.BigInteger;

public class FibonacciMemo {
    private static HashMap<Integer, BigInteger> map = new HashMap<Integer, BigInteger>();
    /**
     * The classic recursive implementation with no memoization. Don't care
     * about graceful error catching, we're only interested in performance.
     * 
     * @param n
     * @return The nth fibonacci number
     */
    public static int fibNoMemo(int n) {
        if (n <= 1) {
            return n;
        }
        return fibNoMemo(n - 2) + fibNoMemo(n - 1);
    }
    /**
     * Your optimized recursive implementation with memoization. 
     * You may assume that n is non-negative.
     * 
     * @param n
     * @return The nth fibonacci number
     */
    public static BigInteger fibMemo(int n) {
        // YOUR CODE HERE
        if (n <= 1){
            return BigInteger.valueOf(n);
        }

        if (!map.containsKey(n)){
            map.put(n, fibMemo(n-1).add(fibMemo(n-2)));
        }
        return map.get(n);        
    }
public static void main(String[] args) {
        // Optional testing here        
        String m = "Fibonacci's real name was Leonardo Pisano Bigollo.";
        m += "\n" + "He was the son of a wealthy merchant.\n";
        System.out.println(m);
         System.out.println("300: " + FibonacciMemo.fibMemo(300));
        System.out.println("8000: " + FibonacciMemo.fibMemo(8000));
        // 46th Fibonacci = 1,836,311,903
        // 47th Fibonacci = 2,971,215,073
    }
}

Answer 1

您的代码有两个问题。显而易见的一个是堆栈消耗。记忆化确实将时间复杂度从指数级降低到线性级，但该方法仍然具有线性堆栈消耗 - 对于 8000 的输入值，它分配 8000 个堆栈帧。

如 docs 中所述，每个线程的默认堆栈大小为 320kB，这足以满足大约 1000 - 2000 帧，这还不够。您可以使用 -Xss JVM 开关增加堆栈大小，但这仍然不是万无一失的。您应该改用迭代实现。

第二个问题是您的静态缓存永远不会被清除，这基本上会导致内存泄漏。您可以将递归方法包装在另一个方法中，该方法在递归终止后清除散列映射，但这会降低一些性能，因为不能在后续调用中重用一次调用的结果。

一个更高效的解决方案是使用不需要手动清理的适当缓存实现，但可以自行处理大小限制和垃圾收集。 Guava提供了这样的实现。