haskell - 使用 haskell 投影 euler 25 的缓慢解决方案

Question

我是 Haskell 语言的新手，为了学习，我想我会加入一些 Project Euler。在 Project 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

So my question is what is wrong in the first approach that is making it so slow.

您的第一种方法在 stepper 的定义中有一个无限循环，但是尽管如此，由于指数分支策略，即使没有无限循环也会花费相当多的时间。

---

您的第一种方法会导致指数递归。事实上，除了这两个基本情况，所有其他情况都会导致两次额外的调用:

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

因此，这意味着对于 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 函数被定义为无限循环。事实上，您的函数的一个更详细的变体是:

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

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

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

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

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

---

另一方面，您的第二个斐波那契程序生成一个列表，并重复使用列表中的结果。 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 …

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