0

この単純な「ベンチマーク」を検討してください。

n :: Int
n = 1000
main = do
    print $ length [(a,b,c) | a<-[1..n],b<-[1..n],c<-[1..n],a^2+b^2==c^2]

および適切なCバージョン:

#include <stdio.h>

int main(void)
{
    int a,b,c, N=1000;
    int cnt = 0;

    for (a=1;a<=N;a++)
        for (b=1;b<=N;b++)
            for (c=1;c<=N;c++)
                if (a*a+b*b==c*c) cnt++;
    printf("%d\n", cnt);
}

コンパイル:

  • Haskell バージョンは次のようにコンパイルされます: ghc -O2 triangle.hs(ghc 7.4.1)
  • C バージョンは次のようにコンパイルされます: gcc -O2 -o triangle-c triangle.c(gcc 4.6.3)

実行時間:

  • Haskell: 実数 4.308 秒
  • C: 1.145 秒リアル

Haskell がほぼ 4 倍遅いほど単純で最適化が容易なプログラムであっても、動作は問題ないのでしょうか? Haskell はどこで時間を無駄にしますか?

4

3 に答える 3

8

Haskell バージョンは、ボックス化された整数とタプルの割り当てに時間を浪費しています。

これは、たとえば haskell プログラムをフラグ付きで実行することで確認できます+RTS -s。私にとって、出力された統計には次のものが含まれます。

  80,371,600 bytes allocated in the heap

コンパイラはボックス化されていない整数を使用し、タプルの割り当てをスキップできるため、C バージョンの単純なエンコーディングは高速です。

n :: Int
n = 1000
main = do
  print $ f n

f :: Int -> Int
f max = go 0 1 1 1
  where go cnt a b c
          | a > max = cnt
          | b > max = go cnt (a+1) 1 1
          | c > max = go cnt a (b+1) 1
          | a^2+b^2==c^2 = go (cnt+1) a b (c+1)
          | otherwise = go cnt a b (c+1)

見る：

  51,728 bytes allocated in the heap

このバージョンの実行時間は、C バージョンに対するものです1.920s。1.212s

于 2012-09-05T11:03:44.130 に答える
4

あなたの「ベンチ」がどれだけ関連性があるかわかりません。リスト内包表記が「使いやすい」という点には同意しますが、2 つの言語のパフォーマンスを比較したい場合は、より公正なテストで比較する必要があります。つまり、おそらく多くの要素のリストを作成し、その長さを計算することは、（トリプルループ）でカウンターをインクリメントすることとはまったく異なります。

したがって、haskell には、ユーザーが行っていることを検出してリストを作成しない優れた最適化機能がいくつかあるかもしれませんが、私はそれに依存するコードを作成しませんし、おそらくそうすべきでもありません。

高速にカウントする必要がある場合、プログラムをそのようにコーディングするとは思わないのに、なぜこのベンチでそれを行うのでしょうか?

于 2012-09-05T10:20:06.123 に答える
3

Haskellは非常にうまく最適化できますが、適切なテクニックが必要であり、自分が何をしているのかを知る必要があります。

このリスト内包表記の構文は洗練されていますが、無駄が多いです。プロファイリングの機会について詳しく知るには、RealWorldHaskell の該当する章を読む必要があります。この正確なケースでは、Intまったく正当な理由もなく、多数のリスト スパインとボックス化された を作成します。ここを参照してください：ベンチマークのタイプ プロファイル

あなたは間違いなくそれについて何かをするべきです。編集: @opqdonut は、これを高速化する方法について良い回答を投稿しました。

ベンチマークを比較する前に、次回はアプリケーションのプロファイリングを行うことを忘れないでください。Haskell を使用すると、慣用的なコードを簡単に記述できますが、多くの複雑さも隠されています。

于 2012-09-05T11:04:02.663 に答える