你知道为什么Go在递归fibonacci上看起来相对较慢吗？
我偶然发现了这个很好的小代码库，它比较了几种编译和解释语言的简单递归斐波那契函数：https://github.com/drujensen/fib。这看起来很公平，因为它在任何地方都不会做任何优化技巧。我知道有更好的方法来使用Go的功能，但我只是想知道，为什么Go似乎比其他编译和静态类型的语言慢得多？我可以在我的机器上用11s确认，它看起来和Go很相似。
回答 2
Stack Overflow用户
发布于 2017-11-25 04:26:28
原因是递归计算的组合爆炸。在算法101中，他们通常解释为什么Dru Jensen的递归算法是计算斐波那契数的可怕方法：http://www.cs.toronto.edu/~gfb/csc104/2016W/Lectures/CSC104.2016W.Week-7.Lecture.Fibonacci.I.pdf。fib过程每次被调用时都会调用自身两次。根据设计，Go没有尾递归：Tail call。根据设计，Go从每个goroutine的一个非常小的堆栈开始，它必须爆炸性地增长。没有一个Go程序员想要使用这个算法，它大约比下一个最慢的慢382,358,169倍，比最快的慢18,593,103,127倍，所以优化，这会牺牲其他地方的性能，是没有意义的。
以下是一些Go基准测试结果：
$ go test fib_test.go -bench=.
BenchmarkDruJensen-8 1 9482482595 ns/op
BenchmarkPeterSO1-8 50000000 24.8 ns/op
BenchmarkPeterSO2-8 2000000000 0.51 ns/opfib_test.go
package main
import (
"fmt"
"testing"
)
// Dru Jensen: https://github.com/drujensen/fib
func fib(n uint64) uint64 {
if n <= 1 {
return 1
} else {
return fib(n-1) + fib(n-2)
}
}
func BenchmarkDruJensen(b *testing.B) {
for i := 0; i < b.N; i++ {
fib(46)
}
}
// PeterSO
func fibonacci1(n int) uint64 {
f := uint64(0)
a, b := uint64(0), uint64(1)
for i := 0; i < n; i++ {
f, a, b = a, b, a+b
if a > b {
break
}
}
return f
}
func BenchmarkPeterSO1(b *testing.B) {
for i := 0; i < b.N; i++ {
fibonacci1(46)
}
}
var fibonaccis = []uint64{
0,
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465,
14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073,
4807526976, 7778742049, 12586269025, 20365011074, 32951280099,
53316291173, 86267571272, 139583862445, 225851433717, 365435296162,
591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881,
6557470319842, 10610209857723, 17167680177565, 27777890035288,
44945570212853, 72723460248141, 117669030460994, 190392490709135,
308061521170129, 498454011879264, 806515533049393, 1304969544928657,
2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464,
14472334024676221, 23416728348467685, 37889062373143906,
61305790721611591, 99194853094755497, 160500643816367088,
259695496911122585, 420196140727489673, 679891637638612258,
1100087778366101931, 1779979416004714189, 2880067194370816120,
4660046610375530309, 7540113804746346429, 12200160415121876738,
}
// PeterSO
func fibonacci2(n int) uint64 {
return fibonaccis[n]
}
func BenchmarkPeterSO2(b *testing.B) {
for i := 0; i < b.N; i++ {
fibonacci2(46)
}
}Stack Overflow用户
发布于 2017-11-28 03:06:44
TL;DR到目前为止，我的结论是，只要Go中没有尾部调用优化，我们可能应该避免递归，主要是为了支持迭代算法。如果不使用递归，Go似乎非常快:-)
出于好奇，我将另一种(更简单的)迭代算法与彼得的版本进行了比较(顺便说一句，您需要将i < n更改为i <= n才能获得正确的斐波那契数46)。有趣的是，如果不使用已编译的变体，在main.go中的顺序很重要。第二个函数调用速度更快。我们需要使用基准测试来获得客观的结果，如下所示：
go test -bench .
BenchmarkFibIt-4 100000000 18.5 ns/op
BenchmarkFibP-4 50000000 29.1 ns/op
BenchmarkFib-4 1 12008314197 ns/op通过不使用变量f而直接使用x，它会变得更快一些;-)令我惊讶的是，运行main.go的未编译变体几乎和编译的变体一样快，有时甚至更快！
到目前为止，我的结论是，我们可能应该避免递归，主要是为了支持迭代算法，只要在Go中没有尾部调用优化。
main.go
package main
import (
"fmt"
"log"
"time"
)
func fib(n int) uint64 {
if n <= 1 {
return 1
}
return fib(n-1) + fib(n-2)
}
func fibIt(n int) uint64 {
var x, y uint64
x, y = 0, 1
for i := 0; i < n; i++ {
// c <- x
x, y = y, x+y
}
return x
}
func fibP(n int) uint64 {
f := uint64(0)
a, b := uint64(0), uint64(1)
for i := 0; i <= n; i++ {
f, a, b = a, b, a+b
if a > b {
break
}
}
return f
}
func main() {
var start time.Time
var elapsed time.Duration
start = time.Now()
fibIt(46)
elapsed = time.Since(start)
fmt.Println("Iterative Fibonacci of 46 took", elapsed)
start = time.Now()
fibP(46)
elapsed = time.Since(start)
fmt.Println("Peter's Iterative Fibonacci of 46 took", elapsed)
start = time.Now()
fib(46)
elapsed = time.Since(start)
fmt.Println("Recursive Fibonacci of 46 took", elapsed)
}main_test.go
package main
import (
"testing"
)
func BenchmarkFibIt(b *testing.B) {
for i := 0; i < b.N; i++ {
fibIt(46)
}
}
func BenchmarkFibP(b *testing.B) {
for i := 0; i < b.N; i++ {
fibP(46)
}
}
func BenchmarkFib(b *testing.B) {
for i := 0; i < b.N; i++ {
fib(46)
}
}https://stackoverflow.com/questions/47479295
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号