我正在尝试编写优化的斐波那契作为分配,以便能够计算fib(300)和fib(8000).这是到目前为止我所拥有的(地图是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
    }
}

解决方法:

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

如docs中所述,每个线程的默认堆栈大小为320kB,足以满足大约1000-2000帧的需求,这还不够.您可以使用-Xss JVM开关来增加堆栈大小,但这仍然不是防弹的.您应该使用迭代实现.

第二个问题是您的静态缓存永远不会清除,这基本上会导致内存泄漏.您可以将递归方法包装在另一种方法中,该方法在递归终止后清除哈希图,但是这会浪费一些性能,因为一个调用的结果不能在以下调用中重用.

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