7

私は当初、「if-then-else」を使用する場合と Haskell のガードを使用する場合で速度に違いがないことを確認する目的で、素数を計算するこの (強引で非効率的な) メソッドを書きました (違いはありません!)。しかし、比較のために C プログラムを作成することにしたところ、次の結果が得られました (Haskell は 25% 以上遅くなりました)。

(次の投稿からコンパイラ呼び出しで mod の代わりに rem を使用し、O3 オプションも使用するというアイデアを得たことに注意してください。

Haskell : Forum.hs

divisibleRec :: Int -> Int -> Bool
divisibleRec i j 
  | j == 1         = False 
  | i `rem` j == 0 = True 
  | otherwise      = divisibleRec i (j-1)

divisible::Int -> Bool
divisible i = divisibleRec i (i-1)

r = [ x | x <- [2..200000], divisible x == False]

main :: IO()
main = print(length(r))

C : main.cpp

#include <stdio.h>

bool divisibleRec(int i, int j){
  if(j==1){ return false; }
  else if(i%j==0){ return true; }
  else{ return divisibleRec(i,j-1); }
}

bool divisible(int i){ return divisibleRec(i, i-1); }

int main(void){
  int i, count =0;
  for(i=2; i<200000; ++i){
    if(divisible(i)==false){
      count = count+1;
    }
  }
  printf("number of primes = %d\n",count);
  return 0;
}

私が得た結果は次のとおりです。

コンパイル時間 

time (ghc -O3 -o runProg Forum.hs)
real    0m0.355s
user    0m0.252s
sys 0m0.040s

time (gcc -O3 -o runProg main.cpp)
real    0m0.070s
user    0m0.036s
sys 0m0.008s

および次の実行時間 :

Ubuntu 32 ビットでの実行時間

Haskell
17984
real    0m54.498s
user    0m51.363s
sys 0m0.140s


C++
number of primes = 17984
real    0m41.739s
user    0m39.642s
sys 0m0.080s

Haskell の実行時間には非常に感銘を受けました。ただし、私の質問は次のとおりです。haskellプログラムを高速化するために何かできることはありますか:

  1. 基礎となるアルゴリズムの変更 (アルゴリズムを変更することで大幅なスピードアップが得られることは明らかですが、パフォーマンスを向上させるために言語/コンパイラ側で何ができるかを理解したいだけです)
  2. llvm コンパイラを呼び出します (これがインストールされていないため)

[編集:メモリ使用量]

Alan のコメントの後、Haskell プログラムはメモリ サイズがゆっくりと大きくなるのに対し、C プログラムは一定量のメモリを使用することに気付きました。最初は、これは再帰に関係していると思っていましたが、gspr は、なぜこれが起こっているのかを以下に説明し、解決策を提供します。Will Ness は、(gspr のソリューションと同様に) メモリが静的なままであることを保証する代替ソリューションを提供します。

[編集:より大きなランのまとめ]

テストされた最大数: 200,000:

(54.498s/41.739s) = Haskell 30.5% 遅い

テストされた最大数: 400,000:

3m31.372s/2m45.076s = 211.37s/165s = Haskell 28.1% 遅い

テストされた最大数: 800,000:

14m3.266s/11m6.024s = 843.27s/666.02s = Haskell 26.6% 遅い

[編集: アランのコード]

これは、再帰を持たず、 200,000 でテストした以前に書いたコードです。

#include <stdio.h>

bool divisibleRec(int i, int j){
  while(j>0){
    if(j==1){ return false; }
    else if(i%j==0){ return true; }
    else{ j -= 1;}
  }
}


bool divisible(int i){ return divisibleRec(i, i-1); }

int main(void){
  int i, count =0;
  for(i=2; i<8000000; ++i){
    if(divisible(i)==false){
      count = count+1;
    }
  }
  printf("number of primes = %d\n",count);
  return 0;
}

再帰がある場合とない場合の C コードの結果は次のとおりです (800,000 の場合)。

再帰あり: 11m6.024s

再帰なし: 11m5.328s

実行可能ファイルは、最大数に関係なく (システム モニターで見られるように) 60kb を使用しているように見えるため、コンパイラがこの再帰を検出していると思われることに注意してください。

4

4 に答える 4

5

これは実際にあなたの質問に答えているわけではありませんが、200000 という数字が大きくなったときのメモリ使用量の増加に関するコメントで質問したことです。

その数が増えると、リストも増えますr。コードのr長さを計算するには、コードの最後にすべてが必要です。一方、C コードはカウンターをインクリメントするだけです。一定のメモリ使用量が必要な場合は、Haskell でも同様のことを行う必要があります。コードは依然として非常に Haskelly であり、一般的には賢明な命題です: が である数のリストは実際には必要ありません。必要なのdivisibleはFalse、 がいくつあるかを知ることだけです。

あなたはで試すことができます

main :: IO ()
main = print $ foldl' (\s x -> if divisible x then s else s+1) 0 [2..200000]

(サンクが構築されるのを回避foldl'するより厳密なfoldlfromです)。Data.List

于 2012-08-19T18:39:45.140 に答える
2

まあ、強打パターンはあなたに非常に小さな勝利をもたらします（llvmもそうですが、あなたはそれを期待していたようです）：

{-# LANUGAGE BangPatterns #-}

divisibleRec !i !j | j == 1         = False

私の x86-64 では、Word32 などの小さな表現に切り替えることで、非常に大きな成果が得られます。

divisibleRec :: Word32 -> Word32 -> Bool
...
divisible :: Word32 -> Bool

私のタイミング：

$ time ./so             -- Int
2262

real    0m2.332s

$ time ./so              -- Word32
2262

real    0m1.424s

これは、 のみを使用している C プログラムにより近いものですint。パフォーマンスに関してはまだ一致していません。その理由を理解するには、コアを調べる必要があると思います。

EDIT：そして、メモリの使用は、すでに述べたように、名前付きリストに関するものrです。をインライン化し、分割できない値ごとrに出力し、合計を取りました。1

main = print $ sum $ [ 1 | x <- [2..800000], not (divisible x) ]
于 2012-08-19T18:38:44.627 に答える
1

アルゴリズムを書き留める別の方法は、

main = print $ length [()|x<-[2..200000], and [rem x d>0|d<-[x-1,x-2..2]]]

残念ながら、動作が遅くなります。テストとして使用all ((>0).rem x) [x-1,x-2..2]すると、さらに遅くなります。それでも、セットアップでテストするかもしれません。

コードを bang パターンの明示的なループに置き換えても、何の違いもありませんでした。

{-# OPTIONS_GHC -XBangPatterns #-}
r4::Int->Int
r4 n = go 0 2 where
  go !c i | i>n = c
          | True = go (if not(divisible i) then (c+1) else c) (i+1)

divisibleRec::Int->Int->Bool
divisibleRec i !j | j == 1 = False 
                  | i `rem` j == 0 = True 
                  | otherwise = divisibleRec i (j-1)
于 2012-08-19T15:33:30.260 に答える
0

Haskell でプログラミングを始めたとき、その速度にも感銘を受けました。この記事のポイント 5「Haskell の速度」を読むことに興味があるかもしれません。

于 2012-08-19T17:26:02.833 に答える