解读费布纳契数列：非递归与记忆递归的计时比较

2024-04-05 00:09

短信预约 -IT技能 免费直播动态提醒

一分耕耘，一分收获！既然打开了这篇文章《解读费布纳契数列：非递归与记忆递归的计时比较》，就坚持看下去吧！文中内容包含等等知识点...希望你能在阅读本文后，能真真实实学到知识或者帮你解决心中的疑惑，也欢迎大佬或者新人朋友们多留言评论，多给建议！谢谢！

问题内容

看完麻省理工学院关于动态规划的讲座后，我想练习一下斐波那契。我首先编写了简单的递归实现，然后添加了记忆功能。这是记忆版本：

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 工具编译 -s 获得），但无济于事。我仍然在记忆版本中看到 call 指令，在我看来，这应该会产生足够的开销来证明它至少比非递归版本稍微优于。

有更懂行的人可以帮助我了解发生了什么吗？

附注我知道整数溢出；我用了10000只是为了增加负载。

谢谢。

正确答案

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

下一点：
编写基准测试很棘手。微小的细节可能对结果产生重大影响。例如。对 printf 的调用很可能需要相当长的时间来执行，但实际上并没有考虑斐波那契计算的运行时间。我没有任何可用的环境来测试这些 io 操作对时序的实际影响有多大，但很可能相当大。特别是因为您的算法运行了相当小的 10000 次迭代，或者仅仅 100 微秒，如 @Brackens answer 中所示。

总结一下：
从基准测试中删除 io，在每次迭代中从空的 memo 开始，并增加迭代次数以获得更好的计时。

我认为您在问为什么记忆递归实现并不比迭代快很多执行。尽管您提到了您没有展示的“朴素递归实现”？

使用基准测试，您可以看到两者的性能具有可比性，也许迭代速度更快一些：

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

我预计你的记忆递归实现不会更快，因为：