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

我是Haskell语言的新手，要学习，我想我会参加一些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

这非常快。

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

最佳答案

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

您的第一种方法在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 …

这样就不会出现分支问题，因为它可以重用列表中已经存在的结果。

关于haskell - 使用Haskell缓慢解决Euler 25项目的问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58012505/