如何使这个斐波纳契功能更快？

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).然后你每次计算这两者的总和并转移:

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

因此,这导致五次调用(针对原始代码的九次调用).当然,调用的数量并不是性能的保证,因为有些方法可以做更多的工作,但是我们的方法与n 成线性比例,而原始方法与n成指数级.因此,即使原始方法的速度快了数千倍,最终调用次数的差异将是巨大的,它将表现得更好.

Answer 2

您可以用记忆来包装它以消除冗余计算

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

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