为什么用不同的方式编写相同的函数有不同的结果时间？

我一直在玩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循环。这是什么造成的？

来源

2016-06-28 Арсен Гоян

“理论上，递归应该或多或少地等于for循环”：这通常不是真的，只适用于尾递归变换的特殊情况由编译器在迭代中。 – Renzo

这是因为您呈现的递归版本会进行大量重复计算。构建一个函数调用的树来查看我的意思。即使对于一个小于4的参数，也要看看有多少函数调用被生成，以便在逻辑的每一个链上到达一个基本情况。

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

有了您的递归函数调用的次数与参数num呈指数增长。

相比之下，你的环形版本num线性增长。它并不需要的nn之前一个非常大的值大于2 ^ň一个很多工作量少。

来源

2016-06-28 14:22:20 pjs

有很多方法可以实现递归;斐波那契函数是一个很好的例子。由于pjs已经指出，经典的双递归定义指数增长。该碱是

φ=（SQRT（5）+1）/ 2 = 1.618+

你NthFibonacci实现以这种方式工作。它的顺序是φ^ n，这意味着对于大的n，调用f（n + 1）需要的时间与f（n）相同。

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

还有其他的方法。例如，动态编程（DP）可以保留先前结果的缓存。在f（4）的情况下，DP实现将仅计算f（2）一次;第二次调用会看到第一次调用的结果是在缓存中，并返回结果而不是进一步调用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)

来源

2016-06-28 16:56:21 Prune

@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}

清理你循环版本，以及（在数学你应该几乎从来不使用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左右）

来源

2016-06-28 18:05:46 agentp

为什么用不同的方式编写相同的函数有不同的结果时间？

回答

相关问题