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，但看起来它每次都会压缩整个列表，所以这不会花费更长的时间。只是计算下一个指数吗？

Answer 1

Haskell中的列表是懒惰的。它们是在使用时计算的，但不会进一步计算。

函数fib1确实计算了整个列表，但是只计算一次，并且只计算到您所要求的索引。

函数fib2做了很多额外的工作:它可能会多次计算元素。

试着用笔和纸来完成它。例如，在fib2 !！5的情况下，列表需要扩展到索引5。计算fib2 !！0和fib2 !！1需要很少的时间，因为它们是常量。下一个元素fib2 !！2的计算方法是:将fib2 !！0和fib2 !！1相加，然后fib2 !！3= fib2 !！1+ fib2 !！2，依此类推。

但。

这里需要注意的最重要的一点是，编译器和/或运行时不会记住fib2函数，这意味着:它不会记住以前的计算。因此，每次代码命中fib2 !! n时，它都会重新开始计算，这与以前做过多少次都没有关系，即使这是在完全相同的(递归)函数调用中发生的。

关于计算效率，您的fib2实现相当于：

fib3' :: Integer -> Integer
fib3' 0 = 0
fib3' 1 = 1
fib3' n = fib3' (n - 2) + fib3' (n - 1)

fib3 :: [Integer]
fib3 = [fib3' n | n <- [0..]]

同样的低效，我只是把列表部分去掉了。

另一方面，fib1利用以前的计算，使用它们来避免重新计算它们。这就是动态编程背后的核心思想:使用一种可用于存储和检索先前计算结果的数据结构，以将潜在昂贵的递归函数调用交换为非常便宜的查找。

Answer 2

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

然后我测试了重新计算10000的时间，它花了同样的时间来计算10001，就好像它计算了10001后记住了所有其余的一样。为了计算第10001次，它不计算10000和9999 (在单独的递归中)，它的行为与您期望的一样，如果它只是对记住的列表进行索引。

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