带有记忆的斐波那契序列仍然比正常的递归解决方案慢

Question

我注意到我的带记忆的递归斐波那契算法只适用于大于 12 的值。

我将它与其他人的方法实现进行了比较，他也用它传递了一个数组。我以为每次传递一个数组，在重新调用方法时会占用太多内存，从而使程序变慢，但事实并非如此。

不知何故，我仍然无法理解我的外部数组为何不比正常的递归斐波那契算法快。我想这可能是因为我的 if 中的许多条件，我检查它是否较慢但我不确定。

如果可能的话，你能看看我的代码并告诉我我做错了什么或者后台发生了什么吗？

public class Fibonacci2 {
    int memory[];

    public Fibonacci2(int f) {  
        if (memory == null) {
            memory = new int[f+1];

            memory[0] = 0;
            memory[1] = 1;
            memory[2] = 1;
        }   
    }
    
    public int recursive(int f) {
        if (memory[f-1] != 0 && memory[f-2] != 0 && f>2) {
            memory[f] = memory[f-1] + memory[f-2];
        } else if (memory[f-1] == 0 && memory[f-2] != 0 && f>2) {
            memory[f] = recursive(f-1) + memory[f-2];
        } else if (f>2) {
            memory[f] = recursive(f-1) + recursive(f-2);
        }

        return memory[f];
    }
    
}

public class Fibonacci1 {
    public Fibonacci1() {}
    
    public int recursive(int f) {
        if (f > 2) {
            return recursive(f-1) + recursive(f-2);
        } else {
            return 1;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        int fibo = 12;

        Fibonacci1 fiboEx1 = new Fibonacci1();
        Fibonacci2 fiboEx2 = new Fibonacci2(fibo);

        int a = fiboEx1.recursive(fibo);

        long start = System.nanoTime();
        long stop = System.nanoTime();

        System.out.println("fibo of " + fibo + " is " + a);
        System.out.println("Fibonacci time without memorization: " + (stop-start));

        int b = fiboEx2.recursive(fibo);

        start = System.nanoTime();
        stop = System.nanoTime();

        System.out.println("fibo of " + fibo + " is " + b);
        System.out.println("Fibonacci time with memorization: " + (stop-start));
    }
}

Answer 1

I noticed that my recursive Fibonacci algorithm with memorization only works for values bigger than 12.

我猜你的意思是写“值小于比 12”。无论哪种方式，这都是不正确的：您的解决方案适用于大于 12 的值，直到结果类型溢出。

也就是说，您的代码存在多个问题。

不要在构造函数中测试 if(memory==null)。总是正确。
memory[f-1] != 0 && memory[f-2] != 0 && f>2 — 你为什么要在这里测试 f > 2？只有在开始时测试它以避免访问负数数组元素时，该测试才有意义。否则测试是多余的。

整个功能比必要的更复杂。分离访问记忆值的逻辑，使其更清晰、更简单、更不易出错：

public int recursive(int f){
    if (f > 2 && memory[f - 2] == 0) {
        memory[f - 2] = recursive(f - 2);
    }
    if (f > 1 && memory[f - 1] == 0) {
        memory[f - 1] = recursive(f - 1);
    }
    memory[f] = memory[f - 2] + memory[f - 1];
    return memory[f];
}

......但是你当然可以而且应该进一步简化它：

public int recursive(int f){
    if (memory[f] == 0) {
        memory[f] = recursive(f - 2) + recursive(f - 1);
    }
    return memory[f];
}

这也是一样的。但不是每个函数调用都对 memoised 值进行多次冗余检查，它只是处理 它自己的 值（即 f 的值），并为其余的调用自身。

从根本上说，将其作为带有构造函数和附加函数的 class 毫无意义：该函数只能用于获取单个值的斐波那契数，这，此外，在构造函数和函数调用中需要相同（这很容易出错！）。例如，以下会使代码崩溃：new Fibonacci2(10).recursive(15)。这样做也是如此：new Fibonacci2(1)。好的代码不会允许这样的错误发生。

这是一个没有这些问题的解决方案：

class Fib {
    static int memory[];

    private static void resizeMemory(int newSize, int[] oldValues) {
        if (newSize < 3) newSize = 3;
        memory = new int[newSize];
        System.arraycopy(oldValues, 0, memory, 0, oldValues.length);
    }

    public static int fib(int n) {
        if (memory == null || memory.length <= n) {
            resizeMemory(n + 1, new int[] {0, 1, 1});
        }

        if (n == 0) return 0;
        if (memory[n] == 0) memory[n] = fib(n - 2) + fib(n - 1);
        return memory[n];
    }
}

但我仍然不会像这样实际编写一个“真正的”斐波那契实现——维护一个全局内存缓存会引入复杂性并且没有任何实际用途。这是一个不使用缓存的高效实现。实际上，如果您计算很多的斐波那契数，它的效率只会降低，即便如此，这也不太可能成为瓶颈。

为了说明，这是它的样子：

private static int fibImpl(int n, int a, int b) {
    if (n == 0) return a;
    if (n == 1) return b;
    return fibImpl(n - 1, b, a + b);
}

public static int fib(int n) {
    return fibImpl(n, 0, 1);
}

带有记忆的斐波那契序列仍然比正常的递归解决方案慢

Fibonacci sequence with memoization still slower than normal recursive solution

java

memory

fibonacci