使用Haskell缓慢解决Euler 25项目的问题

Question

我是Haskell语言的新手，要学习，我想我会参加一些Euler项目。在Euler 25项目中，我们的任务是执行以下操作：

第12个术语F12是包含三个数字的第一个术语。斐波纳契数列中包含1000个数字的第一项的索引是什么？

这是我对问题的解决方案：

fibGen :: Int -> Int
fibGen 0 = 0
fibGen 1 = 1
fibGen n = fibGen (n-1) + fibGen (n-2)

stepper n
  | length (show ( fibGen n )) >= 1000 = n
  | otherwise = stepper n + 1

这里n只是序列的起点。但是这种方法非常慢，在我决定尝试另一种方法之前已经运行了一个多小时。然后我找到了另一个解决方案，如下所示：

fibs = 0:1:(zipWith (+) fibs (tail fibs))
t = 10^999

problem_25 = length w
    where
      w = takeWhile (< t) fibs

这非常快。

所以我的问题是，使它变得如此缓慢的第一种方法有什么问题。

Answer 1

所以我的问题是，使它变得如此缓慢的第一种方法有什么问题。

您的第一种方法在的定义中有一个无限循环stepper，但是，即使没有无限循环，由于采用了指数分支策略，也将花费大量时间。

您的第一种方法导致指数递归。的确，除了两个基本情况以外，所有其他情况都会导致两个额外的调用：

fibGen :: Int -> Int
fibGen 0 = 0
fibGen 1 = 1
fibGen n = fibGen (n-1) + fibGen (n-2)

因此，这意味着fibGen 5例如，我们将其评估为：

fibGen 5
  - fibGen 4
    - fibGen 3
      - fibGen 2
        - fibGen 1
        - fibGen 0
      - fibGen 1
    - fibGen 2
      - fibGen 1
      - fibGen 0
  - fibGen 3
    - fibGen 2
      - fibGen 1
      - fibGen 0
    - fibGen 1

因此，为了进行计算fibGen 5，我们将总共进行15次调用。一供fibGen 4，二供fibGen 3，三供fibGen 2，五供fibGen 1，三供fibGen 0。

每次增加n，通话次数几乎都会增加一倍。显然，对于大型n，呼叫数量是如此之大，以至于现代机器仍然无法处理它。

此外，您的stepper函数被定义为无限循环。确实，您的函数更详细的变化是：

stepper n
  | length (show ( fibGen n )) >= 1000 = n
  | otherwise = (stepper n) + 1

因此，这意味着，如果您计算stepper n，并且约束失败，您将stepper n再次调用，稍后将其添加1到该结果中，但因此会陷入无限循环。

您可以通过添加括号来解决此问题：

stepper n
  | length (show ( fibGen n )) >= 1000 = n
  | otherwise = stepper (n + 1)

现在程序最终将终止，但是由于递归定义中的分支，将花费大量时间。请注意，每次调用时fibGen，它都会再次分支，这意味着即使我们修复了无限循环，如果我们已经调用了它fibGen 5，那么如果以后再调用它fibGen 6，我们将再次进行所有工作以fibGen 5进行计算fibGen 6。因此，我们在这里不使用记忆。

另一方面，您的第二个fibonacci程序会生成一个列表，然后重用列表中的结果。fib因此将评估为：

   0 : 1 : zipWith …
-> 0 : 1 : 1 : zipWith …
-> 0 : 1 : 1 : 2 : zipWith …
-> 0 : 1 : 1 : 2 : 3 : zipWith …
-> 0 : 1 : 1 : 2 : 3 : 5 : zipWith …

因此，它不会受到分支的影响，因为它可以重用列表中已经存在的结果。