fibonacci序列的记忆化仍然比一般的递归解慢

mspsb9vt  于 2021-07-08  发布在  Java
关注(0)|答案(1)|浏览(380)

我注意到我的带记忆的递归斐波那契算法只适用于大于12的值。我和其他人比较了他是如何实现这个方法的,他还用这个方法传递了一个数组。我认为每次传递数组时,在重新调用方法时会占用太多内存,从而使程序变慢,但事实并非如此。不知何故,我仍然无法理解为什么我的外部数组没有比普通的递归斐波那契算法快。我想这可能是因为在我的if的许多条件,我检查它是慢,但我不确定。
如果可能的话,你可以看看我的代码,告诉我我做错了什么,或者在后台发生了什么。

  1. public class Fibonacci2 {
  2. int memory[];
  3. public Fibonacci2(int f) {
  4. if(memory==null){
  5. memory = new int[f+1];
  6. memory[0]=0;
  7. memory[1]=1;
  8. memory[2]=1;
  9. }
  10. }
  11. public int recursive(int f){
  12. if(memory[f-1] != 0 && memory[f-2] != 0 && f>2){
  13. memory[f] = memory[f-1] + memory[f-2];
  14. }else if(memory[f-1] == 0 && memory[f-2] != 0 && f>2){
  15. memory[f] = recursive(f-1) + memory[f-2];
  16. }
  17. else if(f>2){
  18. memory[f] = recursive(f-1) + recursive(f-2);
  19. }
  20. return memory[f];
  21. }
  22. }
  23. public class Fibonacci1 {
  24. public Fibonacci1() {
  25. }
  26. public int recursive(int f){
  27. if(f > 2){
  28. return recursive(f-1)+recursive(f-2);
  29. }else{
  30. return 1;
  31. }
  32. }
  33. }
  34. public class Main {
  35. public static void main(String[] args) {
  36. int fibo = 12;
  37. Fibonacci1 fiboEx1 = new Fibonacci1();
  38. Fibonacci2 fiboEx2 = new Fibonacci2(fibo);
  39. int a = 0;
  40. long start = System.nanoTime();
  41. a = fiboEx1.recursive(fibo);
  42. long stop = System.nanoTime();
  43. System.out.println("fibo of " + fibo + " is " + a);
  44. System.out.println("Fibonacci time without memorization: "+(stop-start));
  45. int b = 0;
  46. start=System.nanoTime();
  47. b = fiboEx2.recursive(fibo);
  48. stop = System.nanoTime();
  49. System.out.println("fibo of " + fibo + " is " + b);
  50. System.out.println("Fibonacci time with memorization: "+(stop-start));
  51. }
  52. }
u59ebvdq

u59ebvdq1#

我注意到我的递归fibonacci算法只适用于大于12的值。
我猜你的意思是写“值小于12”。不管怎样,这都不是真的:您的解决方案适用于大于12的值,直到结果类型溢出为止。
也就是说,您的代码存在多个问题。
不要测试 if(memory==null) 在构造函数中。这总是真的。 memory[f-1] != 0 && memory[f-2] != 0 && f>2 -你为什么要测试 f > 2 在这里?只有在开始测试时才有意义,以避免访问负数组元素。否则测试是多余的。
整个功能比必要的更复杂。分离访问记忆值的逻辑,使其更清晰、更简单、更不容易出错:

  1. public int recursive(int f){
  2. if (f > 2 && memory[f - 2] == 0) {
  3. memory[f - 2] = recursive(f - 2);
  4. }
  5. if (f > 1 && memory[f - 1] == 0) {
  6. memory[f - 1] = recursive(f - 1);
  7. }
  8. memory[f] = memory[f - 2] + memory[f - 1];
  9. return memory[f];
  10. }

  … 当然,你可以而且应该进一步简化:

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

这也一样。但是,不是每个函数调用都对记忆值执行多个冗余检查,而是简单地处理自己的值(即。 f 的),并要求自己的休息。
从根本上说,将它作为一个带有构造函数和附加函数的类是毫无意义的:该函数只能用于获取单个值的fibonacci数,此外,构造函数和函数调用中的fibonacci数必须相同(这很容易出错!)。例如,以下代码崩溃: new Fibonacci2(10).recursive(15) . 这也是: new Fibonacci2(1) . 好的代码不会允许这样的错误发生。
以下是一个不存在这些问题的解决方案:

  1. class Fib {
  2. static int memory[];
  3. private static void resizeMemory(int newSize, int[] oldValues) {
  4. if (newSize < 3) newSize = 3;
  5. memory = new int[newSize];
  6. System.arraycopy(oldValues, 0, memory, 0, oldValues.length);
  7. }
  8. public static int fib(int n) {
  9. if (memory == null || memory.length <= n) {
  10. resizeMemory(n + 1, new int[] {0, 1, 1});
  11. }
  12. if (n == 0) return 0;
  13. if (memory[n] == 0) memory[n] = fib(n - 2) + fib(n - 1);
  14. return memory[n];
  15. }
  16. }

但我还是不会像这样写一个“真正的”斐波那契实现 — 维护一个全局内存缓存会带来复杂性,而且没有真正的用途。这里有一个不使用缓存的高效实现。实际上,如果你计算很多斐波那契数,它的效率只会降低,即使这样,这也不可能成为瓶颈。
为了说明这一点,这里是这样的:

  1. private static int fibImpl(int n, int a, int b) {
  2. if (n == 0) return a;
  3. if (n == 1) return b;
  4. return fibImpl(n - 1, b, a + b);
  5. }
  6. public static int fib(int n) {
  7. return fibImpl(n, 0, 1);
  8. }
展开查看全部

相关问题