使用LINQ生成素數

Question

以下是面試問題：

以下單線程生成並顯示前500個質數的列表。你會如何優化使用並行LINQ它同時仍保持它一個C＃聲明：

MessageBox.Show(string.Join(",", 
    Enumerable.Range(2, (int)(500 * (Math.Log(500) + Math.Log(System.Math.Log(500)) - 0.5))) 
       .Where(x => Enumerable.Range(2, x - 2) 
             .All(y => x % y != 0)) 
       .TakeWhile((n, index) => index < 500))); 

我想介紹AsParallel()以及ParallelEnumerable到查詢，但沒有看到多核機器的任何實實在在的好處。查詢仍然使用一個CPU核心，而其他核心則享受閒暇時間。有人可以提出一種改進措施，可以平均分配所有內核的負載，從而縮短執行時間嗎？

對於發燒友：下面的公式返回一個上限這是保證，如果你選中了這個數字要大於N素數，也就是說，您將會確信求n素數小於它：

UpperBound = N * (Log(N) + Log(Log(N)) - 0.5) //Log is natural log 

Answer 1

這在我的機器上很好。我從未見過全部我的核心直到現在都達到了100％。感謝給我一個藉口發揮:)

我增加了數字，直到我有足夠的時間來衡量（20,000）。

對我造成影響的關鍵選項是將ExecutionMode設置爲ForceParallelism。

因爲我使用NotBuffered合併選項，所以當我完成後我重新對它進行排序。如果你不關心結果的順序（也許你把結果放在HashSet中），這不是必須的。

DegreeOfParallelism和MergeOptions只提供了微小的收益（如果有的話），以在我的機器上的性能。此示例顯示如何在單個Linq語句中使用所有選項，這是原始問題。

var numbers = Enumerable.Range(2, (int)(20000 * (Math.Log(20000) + Math.Log(System.Math.Log(20000)) - 0.5))) 
       .AsParallel() 
       .WithDegreeOfParallelism(Environment.ProcessorCount) 
       .WithExecutionMode(ParallelExecutionMode.ForceParallelism) 
       .WithMergeOptions(ParallelMergeOptions.NotBuffered) // remove order dependancy 
       .Where(x => Enumerable.Range(2, x - 2) 
             .All(y => x % y != 0)) 
       .TakeWhile((n, index) => index < 20000); 
string result = String.Join(",",numbers.OrderBy (n => n)); 

Answer 2

Stopwatch t = new Stopwatch(); 
      t.Start(); 
      var numbers = Enumerable.Range(2, (int)(500 * (Math.Log(500) + Math.Log(System.Math.Log(500)) - 0.5))) 
       .Where(x => Enumerable.Range(2, x - 2) 
             .All(y => x % y != 0)) 
       .TakeWhile((n, index) => index < 500); 
      t.Stop(); 
      MessageBox.Show(t.ElapsedMilliseconds.ToString()); 
      MessageBox.Show(string.Join(",", numbers)); 

它正在3毫秒內進行評估。良好的linq查詢。

Answer 3

您只能檢查的價值SQRT做到這一點（從上面的升級代碼）

var numbers = new[] {2, 3}.Union(Enumerable.Range(2, (int) (i*(Math.Log(i) + Math.Log(Math.Log(i)) - 0.5))) 
              .AsParallel() 
              .WithDegreeOfParallelism(Environment.ProcessorCount) 
              // 8 cores on my machine 
              .WithExecutionMode(ParallelExecutionMode.ForceParallelism) 
              .WithMergeOptions(ParallelMergeOptions.NotBuffered) 
              // remove order dependancy 
              .Where(x => Enumerable.Range(2, (int) Math.Ceiling(Math.Sqrt(x))) 
                   .All(y => x%y != 0)) 
              .TakeWhile((n, index) => index < i)) 
          .ToList(); 

但它是瘋了，當你有一個簡單的極端快alhoritm：

private static IEnumerable<int> GetPrimes(int k) 
{ 
    int n = (int)Math.Ceiling((k * (Math.Log(k) + Math.Log(Math.Log(k)) - 0.5))); 
    bool[] prime = new bool[n + 1]; 
    prime[0] = prime[1] = false; 
    for (int i = 2; i < prime.Length; i++) 
    { 
     prime[i] = true; 
    } 
    for (int i = 2; i*i <= n; ++i) // valid for n < 46340^2 = 2147395600 
     if (prime[i]) 
     { 
      for (int j = i*i; j <= n; j += i) 
       prime[j] = false; 
      yield return i; 
     } 
} 

當然它並不像LINQ那麼好，因爲解決問題並不是一種時髦的方式，但是你應該知道它存在。

Answer 4

對於未來的讀者，這就是我最終的結果。它非常快。在我微不足道的機器上，它會在一秒之內生成首個20,000個素數的列表。

Enumerable.Range(5, (int)(N * (Math.Log(N) + Math.Log(System.Math.Log(N)) - 0.5))) 
      .AsParallel() 
      .WithDegreeOfParallelism(Environment.ProcessorCount) 
      .WithExecutionMode(ParallelExecutionMode.ForceParallelism) 
      .WithMergeOptions(ParallelMergeOptions.NotBuffered) // remove order dependancy 
      .Where(x => Enumerable.Range(2, (int)Math.Ceiling(Math.Sqrt(x))) 
            .All(y => x % y != 0)) 
      .TakeWhile((n, index) => index < N).Concat(new int[] { 2, 3 }.AsParallel()).OrderBy(x => x).Take(N);