爲什麼用不同的方式編寫相同的函數有不同的結果時間？

我一直在玩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

爲什麼用不同的方式編寫相同的函數有不同的結果時間？

回答

相關問題