如何使这个斐波那契函数更快？

Question

这个找到第 n 个斐波那契的函数有效。

a = 1
b = 2

fibonacci :: Int -> Int
fibonacci 1 = a
fibonacci 2 = b
fibonacci n = (fibonacci (n-1)) + (fibonacci (n-2))

但是速度很慢。如果我这样做 map fibonacci [1..] 它真的随着数字的到来而变慢。我猜这是由于使用了多少堆栈和计算的绝对数量而导致的开销 - 将每一个计算到 a 和 b 而不是仅仅将最后两个加在一起。

我怎样才能改进它，使其更快，但仍然使用函数式编程风格？（我绝对是 haskell 和 FP 新手！）我在 Python 中尝试了一些比较闪电般的东西。

即使不比工作代码更受欢迎，也欢迎提示！

Answer 1

问题是这会导致戏剧性的分支。假设您调用 fibonacci 5，那么这将导致以下 调用树 ：

fibonacci 5
    fibonacci 4
        fibonacci 3
            fibonacci 2
            fibonacci 1
        fibonacci 2
    fibonacci 3
        fibonacci 2
        fibonacci 1

如您所见，fibonacci 3 被调用了两次，fibonacci 2 被调用了三次，fibonacci 1 被调用了两次（在这个非常小的示例中）。存在大量重叠：您多次使用相同的参数调用相同的函数。这当然是低效的：一旦你知道 fibonacci 3 是 3，就不需要第二次计算了。当然，在这个非常小的示例中，这并不是真正的问题：计算 fibonacci 3 是纳秒级的事情。但如果您必须多次计算 fibonacci 100，这将产生巨大的影响。冗余调用的数量也呈指数增长（因此这不是一些只对边际产生一些影响的小问题）。

你可以做的是使用累加器：你递归传递的变量并相应地更新。对于斐波那契数列，有两个这样的变量，f(n-2) 和 f(n-1)。然后你每次计算这两个和 shift 所以：

fibonacci :: Int -> Int
fibonacci 1 = a
fibonacci 2 = b
fibonacci n = fib' (n-2) a b
    fib' 0 x y = x+y
    fib' i x y = fib' (i-1) y (x+y)

在这种情况下，调用树将如下所示：

fibonacci 5
    fib' 3 1 2
        fib' 2 2 3
            fib' 1 3 5
                fib' 0 5 8

因此，这导致了五次调用（相对于原始代码的九次调用）。当然，调用次数并不能保证性能，因为有些方法会做更多的工作，但是我们的方法 linearly 与 n 进行了缩放，而原始方法方法指数与 n。所以即使原始方法快了数千倍，最终调用次数的差异也会如此巨大，以至于它会被超越。

Answer 2

你可以用 memoization 来包装它以消除冗余计算

fibonacci = (map fibm [0..] !!)
    where fibm 1 = a
          fibm 2 = b
          fibm n = fibonacci (n-1) + fibonacci (n-2)

对于您给定的 a 和 b 初始值。

Answer 3

您可以使用矩阵乘法在 O(logN) 时间内计算斐波那契数。类似的问题是here。

如何使这个斐波那契函数更快？

How to make this fibonacci function faster?

haskell

functional-programming

fibonacci