algorithm - 斐波那契 : non-recursive vs memoized recursive puzzling timing results

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 -S 获得)，但无济于事。我仍然在内存版本中看到 CALL 指令，在我看来，这应该会产生足够的开销以证明它至少比非递归版本略胜一筹。

有没有知识渊博的人能帮助我理解发生了什么？

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

谢谢。

Answer 1

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

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

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