与C的Fibonacci序列相比,为什么Haskell如此缓慢？

Question

我只是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)

当我fib_seq 40在GHCI中运行此代码以获得更高的数字时,需要花费很长时间来评估它并且我的计算机挂起并且我必须中断.但是,当我在C中写出相同的逻辑时,(我只是打印而不是将其保存在列表中),

#include<stdio.h>

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秒内完成它是不可接受的.

Answer 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]

一些评论:

1. 与您不同,我实现了完全相同的逻辑.我怀疑这是真正的区别; 更多可能的原因,请参阅剩余的评论.
2. 我指定了与算法的C使用相同的类型.你没有,这可能会遇到两个问题:使用Integer而不是Int用于largenum算术,并且具有类多态类型而不是单态类型,在每个函数调用上增加开销.
3. 我编译了.ghci被构建为尽可能快地交互,而不是生成快速代码.
4. 我目前没有安装正确版本的llvm,但它通常会比ghc自己的codegen更好地处理这样的大数字代码.如果它最终比gcc更快,我不会感到惊讶.

当然,使用众所周知的更好的斐波那契算法之一将胜过所有这些无稽之谈.