遞歸GO和斯卡拉

下面的斯卡拉代碼在1.5分鐘內完成，而GO中的等效代碼在2.5分鐘內完成。
直到fib（40）都需要2秒。該差距出現在fib（50）
我得到的印象是，原生GO應該比Scala更快。遞歸GO和斯卡拉

斯卡拉

def fib(n:Int):Long = { 
    n match { 
     case 0 => 0 
     case 1 => 1 
     case _ => fib(n-1) + fib(n-2) 
    } 
}

func fib(n int) (ret int) { 
    if n > 1 { 
     return fib(n-1) + fib(n-2) 
    } 
    return n 
}

斯卡拉優化？
Golang限制？作爲「我的另一輛車是一個幹部」，問題是「在這個特定的微基準測試中，Scala比GO更快嗎？」

忘記斐波那契讓我說我有一個功能，需要遞歸。
斯卡拉在遞歸情況下更勝一籌嗎？

它可能是一個內部編譯器實現，甚至是Scala特定的優化。
如果您知道，請回答。

轉到在循環運行150億在12秒

func fib(n int) (two int) { 
    one := 0 
    two = 1 
    for i := 1; i != n; i++ { 
     one, two = two, (one + two) 
    } 
    return 
}

來源

2014-07-17 ZAky

我沒有看到任何優化，它是指數，遞歸斐波那契的相同例子已被用來顯示如何**不**寫入遞歸函數。看起來，效果是因爲一些實現的細微差別，可能是垃圾回收，也許是內存可用於進程（比如，出於某種原因，在scala中它足夠執行任務，而不是執行）。我會在高峯時檢查記憶力消耗。 – dmitry

由於Scala是JIT編譯的，它可以在幾次遞歸調用之後做一些特殊的記憶。我已經讓JVM在循環展開方面做了一些令人難以置信的優化。 – LinearZoetrope

儘管go代碼被編譯爲機器代碼，但運行時仍然執行所有內存和堆棧管理，因此它與JVM基本相同。我並不驚訝JVM比去更好地優化。 – chendesheng

斯卡拉溶液將消耗堆，因爲它不是尾遞歸（在加入遞歸調用後發生的），但它不應該被創建任何垃圾。

對於這種代碼模式，最可能使用的熱點編譯器（可能是服務器）比Go編譯器更好。

如果你真的好奇，你可以download a debug build of the JVM, and have it print out the assembly code。

來源

2014-07-17 05:44:15

對於Go，使用迭代而不是遞歸。遞歸可以通過迭代使用顯式堆棧來替代。它避免了函數調用和調用堆棧管理的開銷。例如，使用迭代和從50增加至n 1000幾乎不需要花時間：

package main 

import "fmt" 

func fib(n int) (f int64) { 
    if n < 0 { 
     n = 0 
    } 
    a, b := int64(0), int64(1) 
    for i := 0; i < n; i++ { 
     f = a 
     a, b = b, a+b 
    } 
    return 
} 

func main() { 
    n := 1000 
    fmt.Println(n, fib(n)) 
}

輸出：

$ time .fib 
1000 8261794739546030242 
real 0m0.001s 
user 0m0.000s 
sys 0m0.000s

使用適當的算法。避免指數時間複雜性。當性能很重要時，不要使用斐波那契數的遞歸。

參考：

Recursive Algorithms in Computer Science Courses: Fibonacci Numbers and Binomial Coefficients

我們觀察到的支遞歸函數計算效率低下無法適當涵蓋了幾乎所有的教科書計算機科學課程中，前三年的課程。經常使用斐波那契數和二項式係數作爲分支遞歸函數的例子。然而，他們的指數時間複雜性很少被聲明，並且在教科書中從未完全證明。備選線性時間迭代解決方案很少提到。我們給出非常簡單的證明，這些遞歸函數具有指數時間複雜度。

遞歸的定義和算法，使只有一個遞歸調用的有效技術，但如果它使兩個或更多的遞歸調用可以是非常低效的。因此，遞歸方法通常更有用作概念工具，而不是有效的計算工具。本文提供的證明是在渥太華大學成功授課（五年內）至一年級學生。建議遞歸作爲問題解決和定義工具將在第一個計算機科學課程的第二部分中介紹。然而，遞歸編程應該在課程結束時推遲（或者在第二個計算機科學課程開始時可能更好的是），在迭代程序被很好地掌握並且很好地理解了堆棧操作之後。

來源

2014-07-17 09:01:42 peterSO

問題不在於「我怎樣才能更快地計算斐波那契」。問題是「在這個特定的微基準測試中，Scala比GO快得多」。 –

@Myothercarisacadr：仔細閱讀問題。這個問題詢問從fib（40）到fib（50）的時間從2秒到1.5到2.5分鐘。這個答案解決了Go的這個問題。對於Scala來說，這可能類似。 – peterSO

那麼你應該總是使用迭代，如果你可以 - 遞歸是懶惰的程序員工具。 – samthebest

遞歸GO和斯卡拉

回答

相關問題