並行処理は連続処理より高速ではありませんか？</p> <p>アルゴ＃1（パラレル）：

Question

は次の素数を見つけるための戦略を考え出すしようとすると

private static int NextPrime(int p) 
    { 
     int nextP = 2 * p; // there is always a prime between n & 2*n ! 
     Enumerable.Range(p + 1, p) 
        .AsParallel() 
        .ForAll(g => 
        { 
         bool prime = true; 
         for (int i = 2; i <= Math.Sqrt(g); i++) 
         { 
          if (g % i == 0) 
          { 
           prime = false; 
           break; 
          } 
         } 
         if (prime) 
         { 
          if (g < nextP) 
           nextP = g; 
          return; 
         } 
        }); 

     return nextP; 
    } 

アルゴ＃2（シーケンシャル）：

private static int NextPrimeNonParallel(int p) 
    { 
     int nextP = 2 * p; // there is always a prime between n & 2*n ! 
     foreach (var g in Enumerable.Range(p + 1, p)) 
     { 
      bool prime = true; 
      for (int i = 2; i <= Math.Sqrt(g); i++) 
      { 
       if (g % i == 0) 
       { 
        prime = false; 
        break; 
       } 
      } 
      if (prime) 
      { 
       if (g < nextP) 
        nextP = g; 
       return nextP; 
      } 
     } 
     return 0; 
    } 

シーケンシャルよりも大幅に高速でありますパラレル:)なぜ？それとも、私の平行したアルゴは本当によく書かれていますか？

ありがとうございます！

Answer 1

理由は、それが最初の素数を見つけたが、ときにそのFOUNDあなたの非並列バージョンはすぐに最初の値を返しますが、を返す前に全範囲いえます常にループする場合は、並列ForAllが終了していないということです。それが最初の範囲内の素数を見つけたが、それは新しい首相が範囲内で発見されたすべての時間をnextP上書きするので、実際に最後一つを見つけたが返されませんので、

これはまた、並列バージョンバギーを行います。範囲内の最高のプライムではないかもしれないことに注意してください。あなたはタスクを実行しているので、要素が順不同で処理されることがあります。

代わりに、this version of Parallel.ForEachを使用して、すべての繰り返しでParallelLoopStateとなるようにします。 Break()に電話した場合（注意：そのオブジェクトでは、順序が正しくないためにStop（）を実行しても値が大きすぎる可能性があります）、ループは最も早い時点で破損します。また、nextPに書き込むようにする必要があります（すべてのスレッド間で共有されている状態）ので、最小の値しか保存できません。

lock(lockObject) { 
    if(value<nextP) nextP = value; 
} 

このようにすれば、パフォーマンスを向上させて並列実行できるはずです。

Answer 2

@ヨアキムの答えが正しい。私はちょうど2点を追加したい：

• あなたの素性テストアルゴリズムはナイーブである。あなたが本当に大きな数字を扱っていて、本当に速いアルゴリズムを望むなら、複雑であるが漸近的に速いアルゴリズムがあります。たとえば、http://en.wikipedia.org/wiki/AKS_primality_testを参照してください。

• あなたはそれほど複雑さをしたいが、簡単な方法であなたのアルゴリズムを高速化したくない場合は、次の

  1. Mの素数をチェックすると、わずか2で素数にそれを分けます。 .sqrt（M）
  2. まず、2..sqrt（M）のすべての素数を見つけます。
  3. 2番目の手順でリストを記憶して、将来のクエリを高速化します。

  10^12より大きい最小の素数を見つけたいとします。私の提案は、10^6より小さいすべての素数を格納するのに十分な領域があると仮定します。それはまた、10^6ステップより小さいすべての素数が価値あるものであることを見つけるために、多くの同様のクエリを実行することを前提としています。

Answer 3

2つの理由は、並列プログラムが逐次プログラムより遅い理由です。

1：通信オーバーヘッド、すなわちプロセッサまたはスレッド間の情報交換または同期化のための時間、およびアイドル時間（プロセッサが何も役に立たずにイベントが起こるのを待つ時間）のために、また、各プロセッサへの作業の分配が等しく分割されていないことにも依存する。

1. 低いアムダールによれば、プログラムの一部がparalleizedできない場合、最小実行時間、実行のシーケンシャル端数時間未満であることができないので、プロセッサの数を増加させるのに関係なく。