Kann die Ausführungszeit dieses Primzahlgenerators verbessert werden?

Question

Mein erstes Ziel beim Schreiben war es, den kleinstmöglichen Footprint zu ermöglichen. Ich kann mit Zuversicht sagen, dass dieses Ziel erreicht wurde. Leider bleibt mir dabei eine eher langsame Implementierung. Um alle Primzahlen unter 2 Millionen zu generieren, benötigt man auf einem 3Ghz Intel Chip etwa 8 Sekunden.

Gibt es trotzdem eine Verbesserung der Ausführungszeit dieses Codes mit minimalem Verzicht auf den geringen Speicherbedarf? Oder mache ich das aus funktionaler Sicht falsch?

CODE

/// 6.5s for max = 2,000,000 
let generatePrimeNumbers max =  
    let rec generate number numberSequence = 
     if number * number > max then numberSequence else 
     let filteredNumbers = numberSequence |> Seq.filter (fun v -> v = number || v % number <> 0L) 
     let newNumberSequence = seq { for i in filteredNumbers -> i } 
     let newNumber = newNumberSequence |> Seq.find (fun x -> x > number) 
     generate newNumber newNumberSequence     
    generate 2L (seq { for i in 2L..max -> i }) 

aktualisieren

gezwickt ich den Algorithmus und verwaltet 2 Sekunden abrasieren aber doppelt Speicherverbrauch.

/// 5.2s for max = 2,000,000 
let generatePrimeNumbers max =  
    let rec generate number numberSequence = 
     if number * number > max then numberSequence else 
     let filteredNumbers = numberSequence |> Seq.filter (fun v -> v = number || v % number <> 0L) |> Seq.toArray |> Array.toSeq 
     let newNumber = filteredNumbers |> Seq.find (fun v -> v > number) 
     generate newNumber filteredNumbers     
    generate 2L (seq { for i in 2L..max -> i }) 

aktualisieren

Anscheinend ich einen alten Compiler wurde mit. Mit der neuesten Version dauert mein ursprünglicher Algorithmus 6.5s statt 8s. Das ist eine ziemliche Verbesserung.

Answer 1

Tomas Petricek's function ist ziemlich schnell, aber wir können es ein wenig schneller machen.

Vergleichen Sie die folgenden:

let is_prime_tomas n = 
    let ms = int64(sqrt(float(n))) 
    let rec isPrimeUtil(m) = 
     if m > ms then true 
     elif n % m = 0L then false 
     else isPrimeUtil(m + 1L) 
    (n > 1L) && isPrimeUtil(2L) 

let is_prime_juliet n = 
    let maxFactor = int64(sqrt(float n)) 
    let rec loop testPrime tog = 
     if testPrime > maxFactor then true 
     elif n % testPrime = 0L then false 
     else loop (testPrime + tog) (6L - tog) 
    if n = 2L || n = 3L || n = 5L then true 
    elif n <= 1L || n % 2L = 0L || n % 3L = 0L || n % 5L = 0L then false 
    else loop 7L 4L 

is_prime_juliet hat ein wenig etwas schneller inneren Schleife. Es ist eine wohlbekannte Prime-Erzeugungsstrategie, die einen „Toggle“ verwendet nicht-Primzahlen in Schritten von 2 oder 4. Zum Vergleich zu überspringen:

> seq { 2L .. 2000000L } |> Seq.filter is_prime_tomas |> Seq.fold (fun acc _ -> acc + 1) 0;; 
Real: 00:00:03.628, CPU: 00:00:03.588, GC gen0: 0, gen1: 0, gen2: 0 
val it : int = 148933 

> seq { 2L .. 2000000L } |> Seq.filter is_prime_juliet |> Seq.fold (fun acc _ -> acc + 1) 0;; 
Real: 00:00:01.530, CPU: 00:00:01.513, GC gen0: 0, gen1: 0, gen2: 0 
val it : int = 148933 

Meine Version ist über 2.37x schneller, und es ist auch ziemlich nah dran auf die Geschwindigkeit der schnellsten imperativen Versionen. Wir können es machen noch schneller weil wir die Liste der 2L .. 2000000L nicht filtern müssen, können wir die gleiche Strategie verwenden, um eine optimale Abfolge von möglichen Primzahlen zu erzeugen, bevor wir unsere Filter anwenden:

> let getPrimes upTo = 
    seq { 
     yield 2L; 
     yield 3L; 
     yield 5L; 
     yield! (7L, 4L) |> Seq.unfold (fun (p, tog) -> if p <= upTo then Some(p, (p + tog, 6L - tog)) else None) 
    } 
    |> Seq.filter is_prime_juliet;; 
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0 

val getPrimes : int64 -> seq<int64> 

> getPrimes 2000000L |> Seq.fold (fun acc _ -> acc + 1) 0;; 
Real: 00:00:01.364, CPU: 00:00:01.357, GC gen0: 36, gen1: 1, gen2: 0 
val it : int = 148933 

Wir fiel von 1.530s auf 01.364s, so dass wir etwa 1.21x mehr Geschwindigkeit gewannen. Genial!

Answer 2

Ich schrieb eine imperative Version, die schneller ist. Es kann unmöglich sein, Sieve von Eratosthenes rein funktional zu schreiben, um dieselbe Geschwindigkeit zu erreichen, da Sie für jede Zahl einen binären Zustand haben müssen.

let generatePrimes max= 
    let p = Array.create (max+1) true 
    let rec filter i step = 
     if i <= max then 
      p.[i] <- false 
      filter (i+step) step 
    {2..int (sqrt (float max))} |> Seq.map (fun i->filter (i+i) i) |> Seq.length |> ignore 
    {2..max} |> Seq.filter (fun i->p.[i]) |> Seq.toArray 

Answer 3

Nur für Spaß, werfen wir einen Blick auf this page.

pi (x) ist die Primzahlfunktion, sie gibt die Anzahl der Primzahlen unter x zurück.

(x/log x)(1 + 0.992/log x) < pi(x) < (x/log x)(1 + 1.2762/log x) 
// The upper bound holds for all x > 1 

p (x) ist der n-te der Hauptfunktion, die unter Verwendung von angenähert werden kann: Sie können pi (x) unter Verwendung der folgenden Ungleichheiten nähern

n ln n + n ln ln n - n < p(n) < n ln n + n ln ln n 
// for n >= 6 

Mit dem im Verstand, here is a very fast generator, die berechnet die ersten n Primzahlen, wobei jedes Element bei Index i gleich p(i) ist. Also, wenn wir unser Angebot an Primzahlen unter 2.000.000 deckeln wollen, verwenden wir die Oberegrenze Ungleichheit für die Primzahlfunktion:

let rec is_prime (primes : int[]) i testPrime maxFactor = 
    if primes.[i] > maxFactor then true 
    else 
     if testPrime % primes.[i] = 0 then false 
     else is_prime primes (i + 1) testPrime maxFactor 

let rec prime_n (primes : int[]) primeCount testPrime tog = 
    if primeCount < primes.Length then 
     let primeCount' = 
      if is_prime primes 2 testPrime (float testPrime |> sqrt |> int) then 
       primes.[primeCount] <- testPrime 
       primeCount + 1 
      else 
       primeCount 
     prime_n primes primeCount' (testPrime + tog) (6 - tog) 

let getPrimes upTo = 
    let x = float upTo 
    let arraySize = int <| (x/log x) * (1.0 + 1.2762/log x) 
    let primes = Array.zeroCreate (max arraySize 3) 
    primes.[0] <- 2 
    primes.[1] <- 3 
    primes.[2] <- 5 

    prime_n primes 3 7 4 
    primes 

Cool! Wie schnell ist es? Auf meinem 3,2 GHz Quad-Core, erhalte ich nach dem in fsi:

> let primes = getPrimes 2000000;; 
Real: 00:00:00.534, CPU: 00:00:00.546, GC gen0: 0, gen1: 0, gen2: 0 

val primes : int [] = 
    [|2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71; 
    73; 79; 83; 89; 97; 101; 103; 107; 109; 113; 127; 131; 137; 139; 149; 151; 
    157; 163; 167; 173; 179; 181; 191; 193; 197; 199; 211; 223; 227; 229; 233; 
    239; 241; 251; 257; 263; 269; 271; 277; 281; 283; 293; 307; 311; 313; 317; 
    331; 337; 347; 349; 353; 359; 367; 373; 379; 383; 389; 397; 401; 409; 419; 
    421; 431; 433; 439; 443; 449; 457; 461; 463; 467; 479; 487; 491; 499; 503; 
    509; 521; 523; 541; ...|] 

> printfn "total primes: %i. Last prime: %i" (primes.Length - 1) primes.[primes.Length - 1];; 
total primes: 149973. Last prime: 2014853 

das ist also alle Primzahlen rund 2 Millionen in weniger als einer halben Sekunde :)

Answer 4

Der Imperativ Version von Yin geschrieben ist sehr schnell. Auf meiner Maschine ist es auch etwa 0,5 Sekunden. Wenn Sie jedoch eine einfache funktionale Lösung schreiben möchten, können Sie dies nur schreiben:

let isPrime(n) = 
    let ms = int64(sqrt(float(n))) 
    let rec isPrimeUtil(m) = 
    if m > ms then true 
    elif n % m = 0L then false 
    else isPrimeUtil(m + 1L) 
    (n > 1L) && isPrimeUtil(2L) 

[ 1L .. 2000000L ] |> List.filter isPrime 

Dieses einfach prüft, ob eine Zahl auf 1 milion eine Primzahl für alle Zahlen. Es verwendet keine ausgeklügelten Algorithmen (es ist tatsächlich lustig, dass eine Lösung, die am einfachsten ist, oft gut genug ist!).Auf meinem Computer läuft Ihre aktualisierte Version etwa 11 Sekunden und das dauert etwa 2 Sekunden.

Interessanterweise ist dies sehr einfach zu parallelisieren. Wenn Sie PLINQ verwenden, können Sie die folgende Version schreiben und sie läuft fast doppelt so schnell auf Dual Core. Dies bedeutet, dass es auf Quad Core, könnte es so schnell sein wie die schnellste Lösung aus allen Antworten hier, aber mit minimalem Programmieraufwand :-) (natürlich, mit vier Kernen ist nicht ökologisch, aber .. gut)

[ 1L .. 2000000L ] |> PSeq.ofSeq |> PSeq.filter isPrime |> List.ofSeq 

Die PSeq Funktionen sind Wrapper für PLINQ, die ich für mein Buch erstellt habe. Sie sind in verfügbar.

Answer 5

EDIT: aktualisierte Version unten, benötigt weniger Speicher und ist schneller

Manchmal ist es gut, der Lage sein, Sachen zu mutieren. Hier ist eine, zugegebenermaßen eher imperative Version, die Speicher für Geschwindigkeit handelt. Da dieser Thread in F # eine nette Sammlung von Prime-generierenden Funktionen enthielt, dachte ich, es wäre nett, meins trotzdem hinzuzufügen. Die Verwendung eines BitArray hält die Speicherbelegung in Schach.

open System.Collections 

let getPrimes nmax = 
    let sieve = new BitArray(nmax+1, true) 
    let result = new ResizeArray<int>(nmax/10) 
    let upper = int (sqrt (float nmax)) 
    result.Add(2) 

    let mutable n = 3 
    while n <= nmax do 
     if sieve.[n] then 
      if n<=upper then 
       let mutable i = n 
       while i <= nmax do sieve.[i] <- false; i <- i + n 
      result.Add n 
     n <- n + 2 
    result 

Update:

Der obige Code kann weiter optimiert werden: da sie nur die ungeraden Indizes in dem Sieb verwendet, kann die BitArray durch Indizieren ungerade n als 2 m auf die Hälfte der Größe verringert werden + 1. Die neue Version ist auch schneller:

let getPrimes2 nmax = 
    let sieve = new BitArray((nmax/2)+1, true) 
    let result = new ResizeArray<int>(nmax/10) 
    let upper = int (sqrt (float nmax)) 
    if nmax>1 then result.Add(2) //fixes a subtle bug for nmax < 2 

    let mutable m = 1 
    while 2*m+1 <= nmax do 
     if sieve.[m] then 
      let n = 2*m+1 
      if n <= upper then 
       let mutable i = m 
       while 2*i < nmax do sieve.[i] <- false; i <- i + n 
      result.Add n 
     m <- m + 1 
    result 

Timing (Intel Core Duo 2,33 GHz):

> getPrimes 2000000 |> Seq.length;; 
Real: 00:00:00.037, CPU: 00:00:00.046, GC gen0: 0, gen1: 0, gen2: 0 
val it : int = 148933 
> getPrimes2 2000000 |> Seq.length;; 
Real: 00:00:00.026, CPU: 00:00:00.031, GC gen0: 0, gen1: 0, gen2: 0 
val it : int = 148933