使用 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 …

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

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

Slow solution to project euler 25 using haskell

optimization

haskell

fibonacci