Haskell Fibonacci似乎很慢
Haskell Fibonacci似乎很慢
提问于 2014-12-17 23:55:06
我正在学习Haskell，我写了一个简单的Fibonacci函数：
fib :: Int -> Int
fib 1 = 1
fib 0 = 0
fib n = (fib (n-1)) + (fib (n-2))它看起来编译得很好，并且将这个脚本加载到GHCI REPL中，我可以摆弄几个数字。我试过了
fib 33令人惊讶的是它花了大约4秒才给出结果。(对不起，我还不知道如何在Haskell中对函数计时，所以我自己也算了一下)。
Fib 33并不是特别繁琐。答案是少于400万。所以我假设我的代码写得不是很好，或者我做递归的方式有一些问题(嗯，它写得不好，因为它没有考虑负整数)。问题是，为什么它是慢的？感谢您的帮助。
回答 3
Stack Overflow用户
回答已采纳
发布于 2014-12-17 23:59:24
评估花费的时间比您预期的要长，因为您的函数没有使用memoization。有关如何在this question中使用记忆化定义斐波纳契函数的答案，请参阅例如that question或Haskell。
Stack Overflow用户
发布于 2014-12-18 00:00:55
你有没有把这段时间和其他语言做过比较？
这是一个复杂度为O(2^n)的递归算法。在n=33，这带来了惊人的呼叫量。如果你计算每一个这样的调用有多少毫秒或纳秒，你会得到一个关于实际性能的非常显著的答案。
请记住，一些编译器/执行环境可能会缓存函数返回值(Frerich对它的调用方式有更好的内存: memoization)，这极大地提高了此算法的性能。在这种情况下，它不会发生，所以所有的2^n递归调用都会发生。
Stack Overflow用户
发布于 2018-12-20 03:36:56
这是一个带有helper函数的优化版本。仍然比上面给出的惰性无限列表慢，但对于像我这样的新手来说要简单得多！
fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib' 0 1 2 n
fib' :: Integer -> Integer -> Integer -> Integer -> Integer
fib' a b i n = if i > n then b else fib' b (a + b) (i + 1) n附注:仅适用于正数
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/27529587
复制相关文章
相似问题
腾讯云开发者
