6

私は haskell を初めて使用し、Haskell で func を定義しました。

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 関数の速度を上げる方法はありますか?

4

3 に答える 3

21

以下の理由から、これは奇妙な比較です。

  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++ コードと比較してみてください。

于 2012-07-18T08:30:10.040 に答える
13

最適化してコンパイルしてみてください。-O2 を指定した GHC 7.4.1 を使用すると、プログラムは非常に高速に実行されます。

$ time ./test 
832040

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

とありmain = print (febs 30)ます。

クリス・テイラーの回答におけるポリモーフィズムの考慮事項については、febs 40OPのポリモーフィック・フィボナッチ関数を次に示します。

$ 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

Tikhon Jelvis のコメントによると、スピードアップが に置き換えIntegerた結果なIntのか、それともポリモーフィズムを取り除いた結果なのかを確認するのは興味深いことです。febsDaniel 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
于 2012-07-18T08:28:44.353 に答える
3

次のように関数を書くこともできます。

fibs = 0:1:zipWith (+) fibs (tail fibs)

大きな 'n' がすぐに実行される場合でも、非常に高速です。

Prelude> take 1000 fibs
于 2012-07-18T08:35:14.517 に答える