5

これは 7 か月前からの古い質問です。スタック オーバーフロー者は、アッカーマン関数の計算における Haskell の非効率性はコンパイラ エラーによるものであることに同意しました。

Haskell/GHC では Ackermann は非常に効率が悪い

7 か月後、これは修正されたようです。ack は線形メモリで実行されるように見えますが、実行速度は非常に遅いです。

main = print (ack 4 1)
-- Ackermann function
ack 0 n = n + 1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n - 1))

$ time ./ack
65533

>real   8m53.274s
>user   8m47.313s
>sys    0m4.868s


Processor  2.8 GHz Intel Core i7
Memory  8 GB 1333 MHz DDR3
Software  Mac OS X Lion 10.7.5 (11G63)

これについての洞察を求めているだけです。より詳細なものは支持されます。私は関数型プログラミングに不慣れであり、末尾再帰と通常の再帰に関する簡単な発言でさえも高く評価され、賛成されることを覚えておいてください。

4

2 に答える 2

9

どのように実行しているのかはわかりませんが、完全なリストは次のとおりだと思います。

  1. 変更のないプログラムと最適化なしのコンパイル。最初の時間: 7 分 29.755 秒

  2. 最適化を使用していないようです。コンパイル時に必ず使用-O2して試してください。-fllvm新しい時間: 1m2.412s

  3. 明示的な型シグネチャを使用し、可能な場合Intは (vs デフォルトのInteger) を使用します。新しい時間: 0m15.486s

したがって、最適化を使用することでほぼ 8 倍のスピードアップ (他のすべてのベンチマークの質問が最適化フラグを使用しないのはなぜですか?!?!?) と、Int代わりにInteger.

于 2013-12-11T22:55:33.017 に答える
2

型シグネチャを に追加ack:

ack :: Int -> Int -> Int

これにより、コードの 2 つの問題が解決されます。

過度に一般的なタイプ

署名がない場合、コンパイラは次の型を派生させます。

ack :: (Eq a, Eq b, Num a, Num b) => a -> b -> b

ack整数だけでなく、すべての数値型に一般化されます。この追加の間接レイヤーにより、コードが遅くなります。

具体ack的な型 ( などInt) を指定すると、この間接性が取り除かれます。

タイプのデフォルト

さらに、あなたの主な行動は次のように書かれていると思います：

main = print (ack 4 1)

あなたackはどの数値型でも動作しますが、どの型を正確に指定していません。これは、タイプのデフォルト設定と呼ばれるプロセスで、GHC が自動的に 1 つを選択することを意味します。

この場合、Integer可変長タイプの を選択します。任意のサイズの数値を処理できるためInteger、マシン サイズの よりもはるかに低速ですInt。

結論

要約する：

  • トップレベルの定義には常に型シグネチャを記述します。
  • 常に でコンパイルし-Wallます。
于 2013-12-11T22:59:22.227 に答える