Utilizzo di LINQ per generare numeri primi

Question

Segue un'interrogazione:

Il seguente dispositivo di sola lettura genera e visualizza l'elenco dei primi 500 numeri primi. Come si ottimizzarlo utilizzando LINQ parallelo, pur mantenendo una SINGOLA C# DICHIARAZIONE:

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))); 

ho provato l'introduzione AsParallel() nonché ParallelEnumerable nella query, ma non ho visto nessun benefici tangibili su macchine multi-core. La query utilizza ancora un core della CPU pesantemente mentre altri core godono del tempo libero. Qualcuno può suggerire un miglioramento che distribuirà il carico equamente su tutti i core e quindi ridurrà i tempi di esecuzione?

Per gli appassionati di: La seguente formula restituisce un limite superiore che è garantito per essere maggiore di N numeri primi, cioè se controlli fino a questo numero, si certo trovare N innesca più piccolo di lui:

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

Answer 1

Questo funziona bene sulla mia macchina. Non ho mai visto lo tutti i i miei core arrivano al 100% fino ad ora. Grazie per avermi dato una scusa per giocare :)

Ho aumentato i numeri fino a quando ho avuto un tempo abbastanza lento da misurare (20.000).

L'opzione chiave che ha fatto la differenza per me è stata l'impostazione di ExecutionMode in ForceParallelism.

Poiché utilizzo un'opzione di unione non bufferata, la ri-ordina quando ho finito. Questo non sarebbe necessario se non ti interessa l'ordine dei risultati (forse stai mettendo i risultati in un HashSet).

DegreeOfParallelism e MergeOptions hanno fornito solo guadagni minori (se presenti) alle prestazioni sulla mia macchina. Questo esempio mostra come utilizzare tutte le opzioni in una singola istruzione Linq, che era la domanda originale.

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)); 

Sta valutando in 3 millisecondi. Buona query su linq.

Answer 3

È possibile controllare solo SQRT di valore a farlo (codice aggiornato da sopra)

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(); 

ma è pazzo quando si dispone di un semplice ed estremamente veloce 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; 
     } 
} 

ovviamente non è buono come LINQ perché non è un modo alla moda per risolvere un problema, ma dovresti sapere che esiste.

Answer 4

Per i futuri lettori, questo è quello che ho trovato. È piuttosto veloce Sulla mia umile macchina, genera la lista dei primi 20.000 numeri primi sotto un secondo.

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);