为什么递归列表在Haskell中很慢？ [英] Why the recursive list is so slow in haskell？

问题描述

  febs ::（积分a）=>在Haskell中我很新鲜，我在Haskell中定义了一个func： ; a  - > a 
 febs n 
 | n< = 0 = 0 
 | n == 1 = 1 
 | n == 2 = 1 
 |否则= febs（n-1）+ febs（n-2）
  

但它运行速度很慢，当我做febs 30时，需要大约10s，
，而且我在C ++中做的功能相同，运行速度非常快。

<$ p $ （n == 1 || n == 2）
{
return 1;


$
}
返回febs（n-1）+ febs（n-2）;
}

有什么方法可以提升我的haskell func速度吗？

解决方案

这是一个奇怪的比较，原因如下：

1. 你不会说你是在编译Haskell代码，还是在用什么选项。如果你只是用ghci来运行它，那当然会很慢 - 你将解释的代码与编译的代码进行比较。

你的Haskell代码是多态，而你的C ++代码是单形的（也就是说，你已经使用了一个类型类 Integral a => a - > a 而不是具体类型 Int - > Int ）。因此，你的Haskell代码比你的C ++代码更普遍，因为它可以处理任意大的整数，而不仅限于 Int 的范围。编译器可能会优化它，但我不确定。
2. 
   

如果我把下面的代码在一个文件中fib.hs

  fibs :: Int  - > Int 
 fibs n = if n< 3然后1 else fibs（n-1）+ fibs（n-2）
 
 main = print（fibs 30）
  

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

I am fresh in haskell, and I defined a func in Haskell :

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

but, it runs so slow, and when I do "febs 30", it will take about 10s, and I do the same func in C++, it runs very fast.

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

Is there any way to promote my haskell func speed?

解决方案

This is an odd comparison, for the following reasons:

1. You don't say whether you're compiling the Haskell code, or with what options. If you're just running it in ghci, then of course it will be slow - you're comparing interpreted code with compiled code.

2. Your Haskell code is polymorphic whereas your C++ code is monomorphic (that is, you've used a type class Integral a => a -> a instead of the concrete type Int -> Int). Your Haskell code is therefore more general than your C++ code, because it can handle arbitrarily large integers instead of being restricted to the range of an Int. It's possible that the compiler will optimize this away, but I'm not certain.

If I put the following code in a file fib.hs

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

main = print (fibs 30)

and compile it with ghc -O2 fib.hs then it runs fast enough that it appears instantaneous to me. You should try that, and see how it compares with the C++ code.

这篇关于为什么递归列表在Haskell中很慢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！