recursion - 为什么 Go 计算斐波那契递归这么快？

Question

这不是它的正确版本，我只是在玩围棋，但我对围棋计算斐波那契数列中第 42 个(实际上是 43 个)数的速度如此之快感到震惊。

有人可以解释一下为什么计算得这么快吗？我试着将它与 python 进行比较(我知道它比其他语言慢)但是 python 花了 > 1 分钟，我不得不打破递归。

package main

import "fmt"

func fib(a uint) uint {
    if a <= 1 {
        return 1
    }
    return fib(a-1) + fib(a-2)
}

func main() {
    fmt.Println(fib(42))
}


[ `go run Hello.go` | done: 2.316821835s ]
433494437

Answer 1

它的编译器不如 C 的编译器聪明或成熟(至少现在还没有)，但 Go 在时间性能上仍然比 Python 更接近 C(空间性能是另一回事，而不是你问的)。作为一种编译型语言而不是一种解释型语言，它在时间性能上比 Python 有了很大的提升(而且它仍然比 PyPy 一般快，但快不了多少)。

为什么编译型语言通常比解释型语言提供更好的时间性能已在其他地方详细介绍。您可以在 stackoverflow 和互联网上的其他地方研究这个问题。例如，这里是 TL;DR in one stackoverflow answer对于那个问题:

Native programs run using instructions written for the processor they run on.

这里是 TL;DR in another answer :

Interpreted languages are slower because their method, object and global variable space model is dynamic

如果您查找的话，您还可以找到大量基准案例研究和比较不同语言实现的结果。

Go 编译器和 Go 工具链的性能改进也经常进行，您可以在发行说明(和其他地方)中阅读这些信息，例如 this excerpt about version 1.8 :

The new back end, based on static single assignment form (SSA), generates more compact, more efficient code and provides a better platform for optimizations such as bounds check elimination. The new back end reduces the CPU time required by our benchmark programs by 20-30% on 32-bit ARM systems.