haskell - Haskell 动态程序效率

Question

我正在学习更多关于动态编程的知识，并试图在 haskell 中实现它。我正在用不同的方法编写算法进行测试，发现一种比另一种更快。这是斐波那契问题

fib1 :: [Integer]
fib1 = 0:1:zipWith (+) fib1 (tail fib1)

fib2 :: [Integer]
fib2 = 0:1:[(fib2 !! (n-1)) + (fib2 !! (n-2)) | n <- [2..]]

fib1 比 fib2 快得多，但我不知道为什么。fib2 看起来很直观，第 n 个数字是 (n-1)st 加上 (n-2)nd。我得到了 fib1，但看起来它每次都在压缩整个列表，所以不会花费更长的时间。只是计算下一个索引？

标签： haskelldynamicfibonacci

Answer 1

@netom 抱歉，但我认为这不是正在发生的事情。我按时进行了一些测试，计算出第 10000 个数字需要 0.7 秒。在同一次运行中，可以立即计算出第 10000 + 9999（第 10001 个数字），表明它被记住了。

然后，我测试了新计算第 10001 个所需的时间，计算第 10001 个所需的时间与计算第 10000 个并记住所有其余部分的时间相同。要计算第 10001 个，它不会计算 10000 和 9999（在单独的递归中），它的行为就像你期望的那样，如果它只是索引了记住的列表。

然而，递归函数需要几乎两倍的时间！所以他们都正确地使用了动态编程。但正如我发现的那样，fib2 每一步都需要 O(n) 来访问数组，但 fib1 每一步都需要 O(1) 压缩它。