为什么递归列表在haskell中如此之慢？

Question

我在haskell中很新鲜,我在Haskell中定义了一个函数:

febs :: (Integral a)=> a -> a
febs n 
    | n<=0 =0
    | n==1 =1
    | n==2 =1
    | otherwise =febs(n-1)+febs(n-2)

但是,它运行速度很慢,当我做"febs 30"时,它需要大约10秒,而且我在C++中执行相同的功能,它运行速度非常快.

int febs(int n)
{
    if(n == 1 || n ==2)
    {
        return 1;
    }
    return febs(n-1)+febs(n-2);
}

有没有办法提升我的haskell功能速度？

Answer 1

这是一个奇怪的比较,原因如下:

1. 您没有说您是在编译Haskell代码还是使用哪些选项.如果你只是在ghci中运行它,那么它当然会很慢 - 你将解释的代码与编译的代码进行比较.

2. 您的Haskell代码是多态的,而您的C++代码是单态的(也就是说,您使用的是类型类Integral a => a -> a而不是具体类型Int -> Int).因此,您的Haskell代码比C++代码更通用,因为它可以处理任意大的整数而不是限制在一个范围内Int.编译器可能会优化它,但我不确定.

如果我将以下代码放在文件fib.hs中

fibs :: Int -> Int
fibs n = if n < 3 then 1 else fibs (n-1) + fibs (n-2)

main = print (fibs 30)

并编译它ghc -O2 fib.hs然后它运行得足够快,它对我来说是瞬间的.你应该尝试一下,看看它与C++代码的比较.

Answer 2

尝试使用优化进行编译.使用带有-O2的GHC 7.4.1,您的程序运行得非常快:

$ time ./test 
832040

real    0m0.057s
user    0m0.056s
sys     0m0.000s

这是main = print (febs 30).

关于Chris Taylor答案中的多态性考虑,这里febs 40有OP的多态Fibonacci函数:

$ time ./test 
102334155

real    0m5.670s
user    0m5.652s
sys     0m0.004s

这是一个非多态的,即OP的签名替换为Int -> Int:

$ time ./test 
102334155

real    0m0.820s
user    0m0.816s
sys     0m0.000s

每吉洪Jelvis'评论,这将会是有趣的,如果增速是由于更换Integer用Int,或由于摆脱多态性.这是同一个程序,除了febs根据Daniel Fischer的评论移动到一个新文件,并与febs :: Integer -> Integer:

$ time ./test 
102334155

real    0m5.648s
user    0m5.624s
sys     0m0.008s

同样,febs在一个不同的文件中,并具有与最初相同的多态签名:

$ time ./test 
102334155

real    0m16.610s
user    0m16.469s
sys     0m0.104s