Kann die Ausführungszeit dieses Primzahlgenerators verbessert werden?

Question

Mein ursprüngliches Ziel beim Verfassen dieses Artikels war es, einen möglichst kleinen Fußabdruck zu hinterlassen. Ich kann mit Sicherheit sagen, dass ich dieses Ziel erreicht habe. Leider führt dies zu einer recht langsamen Implementierung. Um alle Primzahlen unter 2 Millionen zu generieren, braucht man auf einem 3Ghz Intel Chip etwa 8 Sekunden.

Gibt es eine Möglichkeit, die Ausführungszeit dieses Codes zu verbessern, ohne den geringen Speicherbedarf zu beeinträchtigen? Oder gehe ich von einem funktionalen Standpunkt aus betrachtet die Sache falsch an?

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

Update

Ich habe den Algorithmus optimiert und konnte so 2 Sekunden einsparen, aber den Speicherverbrauch verdoppeln.

/// 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 })

Update

Offenbar habe ich einen alten Compiler verwendet. Mit der neuesten Version benötigt mein ursprünglicher Algorithmus 6,5s statt 8s. Das ist eine ziemliche Verbesserung.

Answer 1

Die Funktion von Tomas Petricek ist ziemlich schnell, aber wir können es noch ein bisschen schneller machen.

Vergleichen Sie das Folgende:

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 eine geringfügig schnellere innere Schleife. Es handelt sich um eine bekannte Strategie zur Erzeugung von Primzahlen, bei der Nicht-Primzahlen in Schritten von 2 oder 4 übersprungen werden. Zum Vergleich:

> 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 etwa 2,37x schneller und kommt der Geschwindigkeit der schnellsten imperativen Versionen ziemlich nahe. Wir können es schaffen noch schneller denn wir brauchen die Liste der 2L .. 2000000L können wir die gleiche Strategie anwenden, um eine optimalere Folge möglicher Primzahlen zu erzeugen, bevor wir unseren 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 sind von 1,530s auf 01,364s gefallen, also haben wir etwa 1,21x mehr Geschwindigkeit erreicht. Fantastisch!

Answer 2

Schauen wir uns spaßeshalber einmal an diese Seite .

pi(x) ist die Primzahlenzählfunktion, die die Anzahl der Primzahlen unter x zurückgibt. Sie können pi(x) mit Hilfe der folgenden Ungleichungen annähern:

(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 die n-te Primzahlfunktion, die mit Hilfe von approximiert werden kann:

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

In diesem Sinne, Hier ist ein sehr schneller Generator die die ersten n Primzahlen berechnet, wobei jedes Element mit dem Index i gleich p(i) . Wenn wir also unser Array bei Primzahlen unter 2.000.000 begrenzen wollen, verwenden wir die Ungleichung für die Obergrenze der Primzahlzählfunktion:

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 er denn? Auf meinem 3.2ghz Quad-Core, erhalte ich das folgende 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 sind also alle Primzahlen um 2 Millionen in weniger als einer halben Sekunde :)

Answer 3

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

Manchmal ist es gut, wenn man Dinge mutieren kann. Hier ist eine, zugegebenermaßen ziemlich zwingende, Version, die Speicher gegen Geschwindigkeit tauscht. Da sich herausgestellt hat, dass dieser Thread eine nette Sammlung von Funktionen zur Erzeugung von Primzahlen in F# beherbergt, dachte ich, es wäre nett, meine trotzdem hinzuzufügen. Die Verwendung eines BitArrays hält den Speicherverbrauch 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

Aktualisierung:

Der obige Code kann weiter optimiert werden: Da er nur die ungeraden Indizes im Sieb verwendet, kann das BitArray auf die Hälfte der Größe reduziert werden, indem ungerade n als 2m+1 indiziert werden. 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

Taktung (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

Answer 4

Die von Yin gepostete imperative Version ist sehr schnell. Auf meinem Rechner sind es auch nur etwa 0,5 Sekunden. Wenn Sie jedoch eine einfache funktionale Lösung schreiben wollen, können Sie einfach dies 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

Damit wird einfach getestet, ob eine Zahl eine Primzahl für alle Zahlen bis 1 Million ist. Es werden keine ausgeklügelten Algorithmen verwendet (es ist eigentlich lustig, dass die einfachste Lösung oft gut genug ist). Auf meinem Rechner läuft Ihre aktualisierte Version etwa 11 Sekunden und diese etwa 2 Sekunden.

Noch interessanter ist, dass dies sehr einfach zu parallelisieren ist. Wenn Sie PLINQ verwenden, können Sie die unten stehende Version schreiben, und sie wird auf einem Dual-Core-Prozessor fast 2-mal schneller laufen. Das bedeutet, dass sie auf einem Vierkernprozessor genauso schnell sein könnte wie die schnellste Lösung aus allen Antworten hier, aber mit minimalem Programmieraufwand :-) (natürlich ist es nicht ökologisch, vier Kerne zu verwenden, aber na ja)

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

El PSeq Funktionen sind Wrapper für PLINQ, die ich für mein Buch erstellt habe (sie machen die Verwendung von PLINQ von F# aus natürlicher). Sie sind verfügbar in Quellcode für Kapitel 14 .

Answer 5

Ich habe eine imperative Version geschrieben, die schneller ist. Es dürfte unmöglich sein, Sieve of Eratosthenes auf rein funktionale Weise zu schreiben, um die gleiche Geschwindigkeit zu erreichen, da man für jede Zahl einen binären Zustand haben muss.

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