与C的Fibonacci序列相比，为什么Haskell这么慢？
我只是Haskell的初学者。 我编写了一个代码来显示Fibonacci序列中的N个数字。 这是我在Haskell中的代码，
fib_seq 1 = 1:[] fib_seq 2 = 1:1:[] fib_seq n = sum(take 2 (fib_seq (n-1))):fib_seq (n-1) 当我在GHCI中为更高的数字运行此代码（例如fib_seq 40时，需要很长时间来评估它并且我的计算机挂起并且我必须中断。 但是，当我在C中写出相同的逻辑时，（我只是打印而不是将其保存在列表中），
#include int fib_seq (int n){ if(n==1) return 1; else if(n==2) return 1; else return fib_seq(n-1)+fib_seq(n-2); } void print_fib(int n){ if(n==0) return; else printf("%i ", fib_seq(n)); print_fib(n-1); } int main(int argn, char* argc){ print_fib(40); return 0; }
代码非常快。 使用GCC编译时运行大约需要1秒。 Haskell应该比C慢吗？ 我在互联网上查找了其他答案，他们说了一些关于memoization的内容。 我开始Haskell，我不知道这意味着什么。 我所说的是我编写的C代码和Haskell代码都执行相同的步骤，而Haskell比C慢得多，它挂起了我的GHCI。 1-2秒的差异是我永远不会担心的，如果C也花了与Haskell相同的时间，我也不会担心。 但Haskell崩溃和C在1秒内完成它是不可接受的。
使用ghc -O2 test.hs编译的以下程序是您发布的C代码的速度的+/- 2％，使用gcc -O2 test.c编译。
fib_seq :: Int -> Int fib_seq 1 = 1 fib_seq 2 = 1 fib_seq n = fib_seq (n-1) + fib_seq (n-2) main = mapM_ (print . fib_seq) [40,39..1]
一些评论：
- 与您不同，我实现了完全相同的逻辑。 但我怀疑这是真正的区别; 更多可能的原因，请参阅剩余的评论。
- 我指定了与C算法相同的类型。 你没有，这可能会遇到两个问题：使用
Integer而不是Int用于largenum算术，并且具有类多态类型而不是单态类型，在每个函数调用上增加了开销。 - 我编译了。 ghci被构建为尽可能快地交互，而不是生成快速代码。
- 我目前没有安装正确版本的llvm，但它通常会比ghc自己的codegen更好地处理这样的大数字代码。 如果它最终比gcc更快，我不会感到惊讶。
当然，使用众所周知的更好的斐波纳契算法之一将胜过所有这些无稽之谈。
猜猜如果在每次递归时“fib_seq（n-1）”被评估两次会发生什么。 然后尝试这个：
fib_seq 1 = 1:[] fib_seq 2 = 1:1:[] fib_seq n = sum(take 2 f):f where f = fib_seq (n-1)