为什么以不同方式编写的相同函数会产生如此不同的结果时间？

Question

我一直在玩 wolfram 语言并注意到一件事：以不同方式编写的相同函数在时间方面有很大不同。

考虑这两个函数：

NthFibonacci[num_] := 
 If [num == 0 || num == 1, Return[ 1], 
   Return[NthFibonacci[num - 1] + NthFibonacci[num - 2]]
 ]

Fibn[num_] := {
 a = 1; 
 b =  1; 
 For[i = 0, i < num  - 1, i++,
  c = a + b;
  a = b;
  b = c;
  ];
 Return [b];
 }

NthFibonacci[30] 大约需要 5 秒来评估。
Fibn[900 000] 也需要大约 5 秒来评估。
内置的 Fibonacci[50 000 000]

也是如此

我实在想不通为什么三者之间的速度会有这么大的差异。理论上，递归应该或多或少等同于 for 循环。这是什么原因造成的？

Answer 1

这是因为你提供的递归版本做了很多很多的重复计算。构建函数调用树以了解我的意思。即使对于一个小到 4 的参数，也要查看生成了多少函数调用才能到达每个逻辑链的基本情况。

                 f(1)
                /
            f(2)
           /    \
       f(3)      f(0)
      /    \
     /      f(1)
    /
f(4)
    \
     \      f(1)
      \    /
       f(2)
           \
            f(0)

通过递归，函数调用的数量随参数 num 呈指数增长。

相比之下，您的循环版本在 num 中呈线性增长。在 n 比 2ⁿ 少 lot 之前，它不需要非常大的 n 值。

Answer 2

实现递归的方法有很多种；斐波那契函数就是一个很好的例子。正如 pjs 已经指出的那样，经典的双递归定义呈指数级增长。基数是

φ = (sqrt(5)+1) / 2 = 1.618+

您的 NthFibonacci 实现以这种方式工作。它是 φ^n 的阶数，意味着对于大的 n，调用 f(n+1) 需要 φ 次，只要 f(n).

更温和的方法在执行流中只计算每个函数值一次。它不是指数时间，而是线性时间，这意味着调用 f(2n) 的时间是 f(n) 的 2 倍。

还有其他方法。例如，动态规划 (DP) 保留先前结果的缓存。在 pjs f(4) 的情况下，DP 实现只会计算 f(2) 一次；第二次调用会看到第一次的结果在缓存中，return 结果而不是进一步调用 f(0) 和 f(1)。这趋向于线性时间。

也有创建检查点的实现，例如缓存 f(k) 和 f(k)+1，因为 k 可以被 1000 整除。这些实现通过起点不低于期望值太远来节省时间，给出他们是 998 次迭代的上限以找到所需的值。

最终，最快的实现使用直接计算（至少对于较大的数字）并在恒定时间内工作。

φ = (1+sqrt(5)) / 2 = 1.618...
ψ = (1-sqrt(5)) / 2 = -.618...
f(n) = (φ^n - ψ^n) / sqrt(5)

Answer 3

@pjs 指出的问题可以在一定程度上通过让递归函数记住先前的值来解决。（消除 If 也有帮助）

Clear[NthFibonacci]
NthFibonacci[0] = 1
NthFibonacci[1] = 1
NthFibonacci[num_] := 
 NthFibonacci[num] = NthFibonacci[num - 1] + NthFibonacci[num - 2]
NthFibonacci[300] // AbsoluteTiming

{0.00201479, 3.59 10^62}

同时清理你的循环版本（你几乎不应该在 mathematica 中使用 Return）：

Fibn[num_] := Module[{a = 1, b = 1,c},
  Do[c = a + b; a = b; b = c, {num - 1}]; b]

Fibn[300] // AbsoluteTiming

{0.000522175 ,3.59 10^62}

你看到递归形式比较慢，但并不可怕。（注意递归形式也达到了 1000 左右的深度限制）

为什么以不同方式编写的相同函数会产生如此不同的结果时间？

Why does the same function written in different ways have such different results time?

performance

recursion

wolfram-mathematica

wolframalpha

wolfram-language