È possibile migliorare il tempo di esecuzione di questo generatore di numeri primi?

Question

Il mio obiettivo iniziale quando scrivevo questo era di lasciare il minimo ingombro possibile. Posso dire con certezza che questo obiettivo è stato raggiunto. Sfortunatamente, questo mi lascia un'implementazione piuttosto lenta. Per generare tutti i numeri primi sotto i 2 milioni occorrono circa 8 secondi su un chip Intel 3Ghz.

C'è comunque qualche modo per migliorare il tempo di esecuzione di questo codice con il minimo sacrificio sul piccolo spazio di memoria? In alternativa, sto andando in questo modo nel modo sbagliato quando si guarda da un punto di vista funzionale?

CODICE

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

Aggiornamento

ho ottimizzato l'algoritmo e sono riuscito a radersi 2 secondi ma il consumo doppio di memoria.

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

Aggiornamento

A quanto pare, stavo usando un vecchio compilatore. Con l'ultima versione il mio algoritmo originale richiede 6,5 anziché 8 secondi. Questo è un bel miglioramento.

Answer 1

Tomas Petricek's function è abbastanza veloce, ma possiamo renderlo un po 'più veloce.

Confrontare il seguente:

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 ha un ciclo po 'leggermente più veloce interiore. Il suo un noto strategia primaria di generazione che utilizza un "toggle" per saltare i non primi incrementi di 2 o 4. Per fare un confronto:

> 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 

La mia versione è di circa 2.37x più veloce, e la sua anche abbastanza vicino alla velocità delle versioni imperative più veloci. Siamo in grado di rendere ancora più veloce perché non abbiamo bisogno per filtrare l'elenco dei 2L .. 2000000L, possiamo usare la stessa strategia per generare una sequenza più ottimale dei possibili numeri primi prima che noi applichiamo il nostro filtro:

> 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 

Noi è sceso da 1,530 a 01,364, quindi abbiamo guadagnato circa 1,21 volte più velocità. Eccezionale!

Answer 2

Ho scritto una versione imperativa, che è più veloce. Potrebbe essere impossibile scrivere il Sieve di Eratostene in un modo puramente funzionale per ottenere la stessa velocità poiché è necessario avere uno stato binario per ogni numero.

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

Solo per funsies, diamo uno sguardo a this page.

pi (x) è la funzione di conteggio principale, restituisce il numero di primi sotto x. È possibile approssimare pi (x) utilizzando i seguenti disuguaglianze:

(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) è la funzione primaria del all'ennesima potenza, che può essere approssimata utilizzando:

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

Con questo in mente, here is a very fast generator che calcola il primo n primo, in cui ogni elemento nell'indice i equivale a p(i). Quindi, se vogliamo coronare la nostra gamma al di sotto numeri primi 2.000.000, usiamo la disuguaglianza upperbound per la funzione di conteggio primaria:

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! Quindi quanto è veloce? Sul mio 3.2GHz quad-core, ottengo il seguente 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 

Ecco tutti i numeri primi circa 2 milioni in meno di mezzo secondo :)

Answer 4

La versione imperativo inviato da Yin è molto veloce. Sulla mia macchina è anche a circa 0,5 secondi. Tuttavia, se si vuole scrivere una soluzione semplice e funzionale si può semplicemente scrivere questo:

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 

Questa verifica semplicemente se un numero è un numero primo per tutti i numeri a 1 milione. Non usa algoritmi sofisticati (è davvero divertente che una soluzione che sia la più semplice spesso sia abbastanza buona!).Sulla mia macchina, la versione aggiornata viene eseguita per circa 11 secondi e dura circa 2 secondi.

Più interessante, questo è molto facile da parallelizzare. Se usi PLINQ puoi scrivere la versione qui sotto e funzionerà quasi 2 volte più velocemente su dual core. Ciò significa che su quad core, potrebbe essere veloce come la soluzione più veloce da tutte le risposte qui, ma con uno sforzo minimo di programmazione :-) (ovviamente, l'utilizzo di quattro core non è ecologico, ma .. bene)

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

Le funzioni PSeq sono wrapper per PLINQ che ho creato per il mio libro (rende più naturale l'utilizzo di PLINQ da F #). Sono disponibili in .

Answer 5

EDIT: versione aggiornata di seguito, utilizza meno memoria ed è più veloce

A volte è bello essere in grado di mutare roba. Ecco una versione, certamente piuttosto imperativa, che scambia la memoria per la velocità. Dato che questo thread è stato pubblicato per ospitare una bella raccolta di prime funzioni generatrici in F #, ho pensato che sarebbe stato carino aggiungere il mio comunque. L'utilizzo di un BitArray consente di mantenere sotto controllo la memoria.

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 

Aggiornamento:

Questo codice può essere ottimizzato ulteriormente: poiché usa soltanto gli indici dispari nel setaccio, il BitArray può essere ridotto a metà della dimensione indicizzando n dispari come 2m + 1. La nuova versione è anche più veloce:

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