斐波那契：非递归与记忆递归令人费解的时序结果

Question

在观看了麻省理工学院关于动态编程的讲座后，我想用斐波那契进行一些练习。我首先编写了幼稚的递归实现，然后添加了记忆。以下是备忘录版本：package mainimport (    "fmt")func fib_memoized(n int, memo map[int]int64) int64 {    memoized, ok := memo[n]    if ok {        return memoized    }    if n < 2 {        return int64(n)    }    f := fib_memoized(n-2, memo) + fib_memoized(n-1, memo)    memo[n] = f    return f}func main() {    memo := make(map[int]int64)    for i := 0; i < 10000; i++ {        fmt.Printf("fib(%d) = %d\n", i, fib_memoized(i, memo))    }}然后，我继续编写该程序的非递归版本：package mainimport (    "fmt")func fib(n int) int64 {    var f1 int64 = 1    var f2 int64 = 0    for i := 0; i < n; i++ {        f1, f2 = f2, f1+f2    }    return f2}func main() {    for i := 0; i < 10000; i++ {        fmt.Printf("fib(%d) = %d\n", i, fib(i))    }}令我感到困惑的是，记忆化版本似乎至少与非递归版本一样好，有时甚至优于它。当然，我期望备忘录与朴素的递归实现相比带来很大的改进，但我只是无法弄清楚为什么/如何备忘录化版本可以与之相提并论，甚至超过其非递归版本。我确实尝试过查看两个版本的汇编输出（通过）获得，但无济于事。我仍然在备忘录版本中看到说明，在我看来，这应该会产生足够的开销来证明它至少略优于非递归版本。go tool compile -SCALL任何知识渊博的人可以帮助我了解发生了什么吗？附言：我知道整数溢出;我使用10000只是为了增加负载。

Answer 1

要记住的一件非常重要的事情是：在测试平台的迭代之间保留。因此，记忆化版本在 中每次迭代循环时最多有两个递归调用。即，您允许记忆化版本在单个迭代之间保留内存，而迭代版本需要在每次迭代中从头开始计算。memomain

下一点：
编写基准测试很棘手。微小的细节可以对结果产生重大影响。例如，调用最有可能需要相当长的时间来执行，但实际上并没有考虑斐波那契计算的运行时。我没有任何环境可用于测试这些 IO 操作实际影响的时序程度，但很可能相当可观。特别是因为你的算法运行的迭代次数相当小，只有10000次迭代，或者只有100微秒，正如@Brackens答案中所看到的那样。printf

总而言之：
从基准测试中删除 IO，在每次迭代中以空开头，并增加迭代次数以获得更好的时机。memo

Answer 2

我想你是在问为什么记忆化的递归实现不比迭代实现快得多。虽然你提到了一个你没有显示的“朴素的递归实现”？

使用基准测试，您可以看到两者的性能相当，也许迭代更快一些：

package kata

import (

    "fmt"

    "os"

    "testing"

)

func fib_memoized(n int, memo map[int]int64) int64 {

    memoized, ok := memo[n]

    if ok {

        return memoized

    }

    if n < 2 {

        return int64(n)

    }

    f := fib_memoized(n-2, memo) + fib_memoized(n-1, memo)

    memo[n] = f

    return f

}

func fib(n int) int64 {

    var f1 int64 = 1

    var f2 int64 = 0

    for i := 0; i < n; i++ {

        f1, f2 = f2, f1+f2

    }

    return f2

}

func BenchmarkFib(b *testing.B) {

    out, err := os.Create("/dev/null")

    if err != nil {

        b.Fatal("Can't open: ", err)

    }

    b.Run("Recursive Memoized", func(b *testing.B) {

        memo := make(map[int]int64)

        for j := 0; j < b.N; j++ {

            for i := 0; i < 100; i++ {

                fmt.Fprintf(out, "fib(%d) = %d\n", i, fib_memoized(i, memo))

            }

        }

    })

    b.Run("Iterative", func(b *testing.B) {

        for j := 0; j < b.N; j++ {

            for i := 0; i < 100; i++ {

                fmt.Fprintf(out, "fib(%d) = %d\n", i, fib(i))

            }

        }

    })

}

% go test -bench=.

goos: darwin

goarch: amd64

pkg: github.com/brackendawson/kata

cpu: Intel(R) Core(TM) i7-8850H CPU @ 2.60GHz

BenchmarkLoop/Recursive_Memoized-12                13424             91082 ns/op

BenchmarkLoop/Iterative-12                         13917             82837 ns/op

PASS

ok      github.com/brackendawson/kata    4.323s

我希望你的记忆递归实现不会快得多，因为：

Go 没有良好的尾部调用优化 （TCO）。正如您可能已经从程序集中看到的那样，仍然有 CAL，如果 CAL 可以优化，则递归通常只会更快。

您的记忆递归实现不是尾部调用，递归调用必须是函数中使用 TCO 的最后一个语句。

Answer 3

这不是你的问题的答案，但有一种方法可以得到log（N）
中的第N个斐波那契数列，你所需要的只是提高矩阵
|0 1 |
|1 1 |
使用二元矩阵幂到 N 的幂

材料链接：
https://kukuruku.co/post/the-nth-fibonacci-number-in-olog-n/
https://www.youtube.com/watch?v=eMXNWcbw75E