java - 如何提高Java递归的速度

Question

问题:如何使用其他技术加速递归方法。

简单的斐波那契数列方法使用递归来输出输入的第 N 个数。

任何建议都会很棒，谢谢。

例如；输入 50 需要近一分钟才能最终得到输出。

编辑:更改问题文本，因为它不是递归太慢，而是我的代码。

public static long cycle(int x) {
  if(x<=1) {
    return x;
  } else {
    return cycle(x-1)+cycle(x-2);
  }
}

Answer 1

让我们思考一下这里的根本问题。您希望代码在相同的硬件上执行得更快，这是一个称为优化的重要软件过程。

在优化过程中，您需要分析您的应用程序以确定最慢的组件并对其进行改进。就您的情况而言，我可以非常肯定地猜测您的程序中最慢的部分是函数调用。绘制第 n 个斐波那契项与我们得到的函数调用次数的关系:

正如您所看到的，增长呈指数级增长。注意:有一些数学方法可以解决这个问题，特别是 this page 中的解释。 。如果您的目的是创建一个快速执行的函数，那么时间复杂度的指数增长总是需要避免的(当然，有些函数必须呈指数增长，但这不是其中之一)。查看cycle(50)，接管了 4 * 10^10 函数调用，您说它在近一分钟内完成，这相当于每秒大约 6.666 亿个函数调用(或每秒 1 次调用) 1.5 ns)，据此称 java 慢似乎不太公平。最重要的是，无论编译器的优化技术有多好或多快，它都无法解决您的时间复杂度，它只能使每个操作稍微快一些(如果您想知道，请阅读 tail-call optimization更多)。

您遇到的主要问题是您多次重新计算相同的斐波那契数，想想您重新计算cycle(2)多少次。这就是指数复杂性的来源，多次重新计算相同的斐波那契数，这是无用的。

解决问题的最简单方法是通过迭代，但您已经表达了对迭代器的不兴趣。

下一个简单的方法是使用查找表 (LUT) 将预先计算的斐波那契数存储在数组中以便快速访问。这种方法的问题可以很容易地显示如下:

上图显示了 n 最大为 10 的 LUT 的影响。虽然我们降低了指数的幂，但我们仍在处理指数，这并不能完全解决问题(假设您需要这样做循环(100)然后呢？)。

解决方案是使用用户 1.618 评论中提到的内存。这意味着在计算每个斐波那契项时保存结果，在计算过程中生成 LUT，永远不会重新计算任何结果两次。

下图演示了此操作的效果:

在 cycle(50) 处，您需要 97 次方法调用，每次调用的速度为 1.5 ns，将在 145.5 ns 内完成，比您眨眼的速度还要快(它可能不会由于需要额外的时间查看 LUT 并且没有进行太多的热身，所以做得那么快)。

在java中实现这个，我们得到:

private static long[] fib_numbers;

public static long cycle(int x){
    if(fib_numbers == null || fib_numbers.length <= x){
        fib_numbers = new long[x + 1];
    }

    return cycle_rec(x);
}

private static long cycle_rec(int x) {
    if(x <= 1){
        return x;
    }else if(fib_numbers[x] != 0){
        // previously computed result exists, return directly

        return fib_numbers[x];
    }else{
        // compute and store cycle(x)
        fib_numbers[x] = cycle_rec(x-1)+cycle_rec(x-2);

        return fib_numbers[x];
    }
}

数组fib_numbers保存我们为每个方法调用动态生成的LUT。我们公开一个公共(public)方法cycle()来设置数组，以便在内部调用cycle_rec()(我们的递归函数)之前使用。