使用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

如果有AsParallel()你的CPU更是創下了100％的上限，然後 - 在你是否能擠出額外的效率了PLINQ問題的精神 - 簡單的答案是沒有。CPU已經成爲你的瓶頸，你的選擇是要得到更好的CPU，或者使用更好的算法。

正如Sami的評論所述，對於算法的幫助，您最好在CodeReview詢問。

Answer 2

從並行的角度來看，沒有什麼可以做得更多 - 您已經將CPU密集型檢查並行執行。

那麼，有沒有什麼明顯的方法來加速？

首先，在CPU綁定方法中有一些明顯的優化。的IsPrime可以製成只檢查奇數除數：

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可以使用整數除法用於檢查數字而不是ToString呼叫（從而避免GC堆分配）：

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

應用這些修剪下來執行時間範圍爲[2, int.MaxValue]，從32.8秒到12.7秒，所以它絕對不是微型優化。

但主要的優化是改變算法。除了生成可能的素數並檢查候選人是否所有數字都是素數，數字本身是素數之外，還可以更改算法以生成所有數字均爲素數的所有可能數字，然後檢查候選人是否爲素數。理由是這樣，候選列表大大減少，並且CPU限制檢查中的一個減少。

生成部分是數字{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); 
    } 
} 

，最終並行方法：

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

現在調用MegaprimeNumbers(2, int.MaxValue).Count()了只有42毫秒，這與最初的32.8秒相比並不算差，我猜。