PLINQを使って余分な効率を搾り取ることは可能でしょうか？

Question

私は、各桁も素数である与えられた範囲内のすべての素数を見つける問題を解決しようとしています。

[1, 100]の範囲では、は、それを満たすすべての数字ですので、8です。2, 3, 5, 7, 23, 37, 53, 37です。

私の現在のソリューションは、

// Yields all the numbers in the range [start, end] that could be primes, 
// by taking into account the fact that a prime is either 2, 3, 6k + 1 or 6k - 1 
static IEnumerable<long> PossiblePrimeNumbers(long start, long end) 
{ 
    if(start <= 2 && end >= 2) 
     yield return 2; 
    if(start <= 3 && end >= 3) 
     yield return 3; 
    for(long n = (start/6 + 1) * 6; ; n += 6) 
    { 
     if((n - 1) <= end) 
      yield return (n - 1); 
     if((n + 1) <= end) 
      yield return (n + 1); 
     else break; 
    } 
} 

// Map for fast checking of whether a digit 0, 1, ..., 9 is a prime 
static bool[] IsPrimeDigit = { false, false, true, true, false, true, false, true, false, false }; 

// True or false depending on whether m is prime 
static bool IsPrime(long m) 
{ 
    long boundary = (long)Math.Floor(Math.Sqrt(m)); 

    bool isPrime = true; 

    for(long i = 2; i <= boundary; ++i) 
    { 
     if(m % i == 0) 
     { 
      isPrime = false; 
      break; 
     } 
    } 

    return isPrime; 
} 

// True or false depending on whether all the digits of m are prime and 
// whether m itself is prime 
static bool IsMegaprime(long m) 
{ 
    return m.ToString().All(c => IsPrimeDigit[c - '0']) && IsPrime(m); 
} 

// Counts the number of "megaprimes" (defined above) in the range [first, last] 
static int NumberMegaprimes(long first, long last) 
{ 
    return PossiblePrimeNumbers(first, last).AsParallel().Count(m => IsMegaprime(m)); 
} 

static void Main(String[] args) 
{ 
    long first = 1; 
    long last = 100; 
    Console.WriteLine(NumberMegaprimes(first, last)); // should print 8 
} 

正しく、あなたも、私が試してみて、それをスピードアップするために.AsParallel()を追加したことがわかります。

これをスピードアップする明確な方法はありますか？ （LINQを取り除く以外）

Answer 1

あなたのCPUは、100％の天井に当たっているAsParallel()との場合 - あなたはPLINQのうち、余分な効率を絞り出すことができるかどうかの質問の精神で - 短い答えはノーですCPUがあなたのボトルネックになり、あなたのオプションはより良いCPUを得るか、より良いアルゴリズムを使用することです。

サミのコメントによれば、アルゴリズムの助けを借りれば、CodeReviewで尋ねるほうがよいでしょう。

Answer 2

並列化の観点からは、何もできることはありません。すでにCPU集中型チェックの実行を並行して移動しています。

これをスピードアップする明確な方法はありますか？

まず、両方のCPUバウンドメソッドに明白な最適化があります。

static bool IsMegaprime(long m) 
{ 
    for (long n = m; n != 0; n /= 10) 
     if (!IsPrimeDigit[n % 10]) return false; 
    return IsPrime(m); 
} 

ダウンこれらトリムを適用する：数字ではなくToStringコール（従ってGCヒープ割り当てを回避する）をチェックするための整数の除算を使用することができ

static bool IsPrime(long m) 
{ 
    if ((m & 1) == 0) return m == 2; // even 
    long boundary = (long)Math.Floor(Math.Sqrt(m)); 
    for (long i = 3; i <= boundary; i += 2) 
     if ((m % i) == 0) return false; 
    return true; 
} 

とIsMegaprime：IsPrimeのみ奇数の除数を確認させることができます範囲[2, int.MaxValue]の実行時間は32.8秒から12.7秒までです。したがって、これは間違いなくマイクロ最適化ではありません。

しかし、主な最適化はアルゴリズムを変更することです。可能な素数を生成し、素数であるすべての数字と素数である数字自体の両方を調べる代わりに、アルゴリズムを変更して、すべての数字を素数ですべての可能な数字を生成し、候補が素数であるかどうかをチェックするだけです。その理由は、候補リストが大幅に削減され、CPUバウンドチェックの1つが削減されるということです。

生成部分は、範囲の末尾までの数字{2,3、5,7}の単純な組み合わせの生成子で、2または5（下位の数字）から始まる複数の数字の組み合わせは、素数でないようにスキップされています。あなたに似た

static readonly int[] oneDigitPrimes = { 2, 3, 5, 7 }; 

static readonly long[] decimalScales = Enumerable.Range(0, 20).Select(n => (long)Math.Pow(10, n)).ToArray(); 

static IEnumerable<long> PossibleMegaprimeNumbers(long start, long end) 
{ 
    var digits = oneDigitPrimes; 
    var scales = decimalScales; 
    var indices = new int[scales.Length]; 
    var results = new long[scales.Length]; 
    long result = 0; 
    int pos = 0, index = 0; 
    while (true) 
    { 
     // Generate next numbers up to end 
     do 
     { 
      var digit = digits[index]; 
      long next = result + digit * scales[pos]; 
      if (next >= start) 
      { 
       if (next > end) break; 
       yield return next; 
      } 
      indices[pos] = index; 
      results[pos] = result; 
      result = next; 
      index = 0; 
      pos++; 
      if (pos == 1 && (digit == 2 || digit == 5)) break; 
     } 
     while (pos < results.Length); 
     // Move back and select next digit 
     do 
     { 
      if (pos == 0) yield break; 
      pos--; 
      index = indices[pos]; 
      result = results[pos]; 
      index++; 
     } 
     while (index >= digits.Length); 
    } 
} 

と、最終的な並列化の方法：

は、私はここで、この問題のために調整1は、反復組み合わせジェネレータのカップルの投稿がありました

static IEnumerable<long> MegaprimeNumbers(long start, long end) 
{ 
    return PossibleMegaprimeNumbers(start, end) 
     .AsParallel() 
     .Where(IsPrime); 
} 

は今MegaprimeNumbers(2, int.MaxValue).Count()を呼び出しますわずか42msで、これは初期の32.8秒と比較して悪い最適化ではないと思います。