1

我正在为 Go 中一种简单的、虚构的编程语言编写一个虚拟机。我正在使用分析器 pprof 来提高性能。我正在用我编造的语言运行斐波那契函数来测试递归函数。

func fib(n) {
    if n < 2 {
        return n
    } else {
        return fib(n-1) + fib(n-2)
    }
}
print fib(34)

当我运行它需要 14 秒，在 Python 中需要 2 秒。这是来自 PProf 的图片。我用绿色突出显示了我的实际程序的函数调用。它们需要 2 秒，另外 12 秒似乎都是 Go 的垃圾收集器。 在此处输入图像描述 有没有办法弄清楚为什么垃圾收集器要花这么多时间？

4

2 回答 2

2

是你的递归算法产生了组合爆炸。使用迭代算法。

试试这个迭代算法：

package main

import "fmt"

// fibonacci returns the Fibonacci number for 0 <= n <= 92.
// OEIS: A000045: Fibonacci numbers:
// F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.
func fibonacci(n int) int64 {
    if n < 0 {
        panic("fibonacci: n < 0")
    }
    f := int64(0)
    a, b := int64(0), int64(1)
    for i := 0; i <= n; i++ {
        if a < 0 {
            panic("fibonacci: overflow")
        }
        f, a, b = a, b, a+b
    }
    return f
}

func main() {
    for _, n := range []int{0, 1, 2, 3, 90, 91, 92} {
        fmt.Printf("%-2d  %d\n", n, fibonacci(n))
    }
}

游乐场： https: //play.golang.org/p/_5CMHZm3Hlo

输出：

0   0
1   1
2   1
3   2
90  2880067194370816120
91  4660046610375530309
92  7540113804746346429

real    0m0.003s
user    0m0.002s
sys     0m0.000s

参考 ：

斐波那契数列和组合爆炸

于 2019-12-29T23:05:04.343 回答
2

正如icza 在评论中指出的那样，实际上将其编译并作为Go代码运行，它运行得非常快：

package main

import (
    "fmt"
    "time"
)

func fib(n int) int {
    if n < 2 {
        return n
    } else {
        return fib(n-1) + fib(n-2)
    }
}

func main() {
    s := time.Now()
    fmt.Println(fib(34))
    d := time.Now().Sub(s)
    fmt.Println("took", d)
}

$ go run fib.go
5702887
took 49.244697ms

（注意：以上是草率的：我们应该使用int64，我只是懒惰）。

Python3 变体：

import time
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

s = time.time()
print(fib(34))
print(f"took {time.time() - s}s")

需要更长的时间：

$ python3 fib.py
5702887
took 2.1027958393096924s

正如peterSO 所指出的，递归算法进行了很多调用：

package main

import (
    "fmt"
    "time"
)

var calls int

func fib(n int) int {
    calls += 1
    if n < 2 {
        return n
    } else {
        return fib(n-1) + fib(n-2)
    }
}

func main() {
    s := time.Now()
    fmt.Println(fib(34))
    d := time.Now().Sub(s)
    fmt.Println("took", d, "to make", calls, "calls")
}

$ go run fib.go
5702887
took 53.328049ms to make 18454929 calls

（额外的几毫秒是由于计算调用）。所以 Go 在大约 50 毫秒内运行了 1845 万次调用，而 Python 在大约 2.1 秒内运行了同样的 1845 万次调用。Go 每次调用大约需要 2.7 ns，Python 每次调用大约需要 114 ms。

于 2019-12-29T23:37:04.407 回答