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

Question

在观看了麻省理工学院关于动态编程的讲座后，我想用斐波那契进行一些练习。我首先编写了幼稚的递归实现，然后添加了记忆。以下是备忘录版本：

package main

import (

    "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 main

import (

    "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 kataimport (&nbsp; &nbsp; "fmt"&nbsp; &nbsp; "os"&nbsp; &nbsp; "testing")func fib_memoized(n int, memo map[int]int64) int64 {&nbsp; &nbsp; memoized, ok := memo[n]&nbsp; &nbsp; if ok {&nbsp; &nbsp; &nbsp; &nbsp; return memoized&nbsp; &nbsp; }&nbsp; &nbsp; if n < 2 {&nbsp; &nbsp; &nbsp; &nbsp; return int64(n)&nbsp; &nbsp; }&nbsp; &nbsp; f := fib_memoized(n-2, memo) + fib_memoized(n-1, memo)&nbsp; &nbsp; memo[n] = f&nbsp; &nbsp; return f}func fib(n int) int64 {&nbsp; &nbsp; var f1 int64 = 1&nbsp; &nbsp; var f2 int64 = 0&nbsp; &nbsp; for i := 0; i < n; i++ {&nbsp; &nbsp; &nbsp; &nbsp; f1, f2 = f2, f1+f2&nbsp; &nbsp; }&nbsp; &nbsp; return f2}func BenchmarkFib(b *testing.B) {&nbsp; &nbsp; out, err := os.Create("/dev/null")&nbsp; &nbsp; if err != nil {&nbsp; &nbsp; &nbsp; &nbsp; b.Fatal("Can't open: ", err)&nbsp; &nbsp; }&nbsp; &nbsp; b.Run("Recursive Memoized", func(b *testing.B) {&nbsp; &nbsp; &nbsp; &nbsp; memo := make(map[int]int64)&nbsp; &nbsp; &nbsp; &nbsp; for j := 0; j < b.N; j++ {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for i := 0; i < 100; i++ {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; fmt.Fprintf(out, "fib(%d) = %d\n", i, fib_memoized(i, memo))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; })&nbsp; &nbsp; b.Run("Iterative", func(b *testing.B) {&nbsp; &nbsp; &nbsp; &nbsp; for j := 0; j < b.N; j++ {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for i := 0; i < 100; i++ {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; fmt.Fprintf(out, "fib(%d) = %d\n", i, fib(i))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; })}% go test -bench=.goos: darwingoarch: amd64pkg: github.com/brackendawson/katacpu: Intel(R) Core(TM) i7-8850H CPU @ 2.60GHzBenchmarkLoop/Recursive_Memoized-12&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 13424&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;91082 ns/opBenchmarkLoop/Iterative-12&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;13917&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;82837 ns/opPASSok&nbsp; &nbsp; &nbsp; github.com/brackendawson/kata&nbsp; &nbsp; 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