Czy można poprawić czas wykonywania tego generatora liczb pierwszych?

Question

Moim początkowym celem podczas pisania tego było pozostawienie możliwie najmniejszego śladu. Mogę powiedzieć z przekonaniem, że ten cel został osiągnięty. Niestety, pozostawia mnie to raczej powolną implementacją. Generowanie wszystkich liczb pierwszych poniżej 2 milionów zajmuje około 8 sekund w układzie Intel 3Ghz.

Czy istnieje jeszcze poprawa czasu wykonania tego kodu przy minimalnym poświęceniu na mały ślad pamięci? Alternatywnie, czy podchodzę do tego w niewłaściwy sposób, patrząc na to z operacyjnego punktu widzenia?

KOD

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

Aktualizacja

I manipulowane algorytmu i udało się ogolił 2 sekund, ale podwójne zużycie pamięci.

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

Aktualizacja

Najwyraźniej używałem starego kompilatora. W najnowszej wersji mój oryginalny algorytm zajmuje 6,5s zamiast 8s. To jest znaczna poprawa.

Answer 1

Tomas Petricek's function jest dość szybki, ale możemy zrobić to trochę szybciej.

Porównaj następujące:

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 ma trochę nieco szybciej wewnętrzną pętlę. Jest to dobrze znana strategia prime-generujący który używa „Przełącz”, aby pominąć niebędące liczb pierwszych w krokach 2 i 4. Dla porównania:

> 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 

moja wersja jest około 2.37x szybszy, a jego również całkiem blisko do prędkości najszybszych imperatywnych wersji. Możemy zrobić to nawet szybciejbo nie trzeba filtrować listę 2L .. 2000000L, możemy użyć tej samej strategii do generowania bardziej optymalną sekwencję możliwych liczb pierwszych zanim zastosujemy nasz filtr:

> 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 

my spadł z 1.530s do 01.364s, więc uzyskaliśmy około 1.21x więcej prędkości. Niesamowite!

Answer 2

Napisałem wersję imperatywną, która jest szybsza. Może być niemożliwe napisanie Sieve of Eratostenes w czysty sposób funkcjonalny, aby osiągnąć tę samą prędkość, ponieważ musisz mieć stan binarny dla każdej liczby.

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

Tylko dla fanów, spójrzmy na this page.

pi (x) jest pierwszą funkcją zliczającą, zwraca liczbę liczb pierwszych poniżej x. Można zbliżenie Pi (x) stosując następujące nierówności:

(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) jest pierwsza funkcja n-tej, która może być przybliżona przy użyciu:

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

Mając to na uwadze, here is a very fast generator którego oblicza pierwsze n liczb pierwszych, gdzie każdy element o indeksie i jest równy p(i). Tak więc, jeśli chcemy cap naszą tablicę na bodźce poniżej 2000000, używamy górna granica nierówności dla funkcji zliczania prime:

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! Jak szybko to działa? Na moim 3.2GHz quad-core, otrzymuję następujący w 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 

Więc to wszystkie liczby pierwsze około 2 milionów w mniej niż pół sekundy :)

Answer 4

Imperatyw wersja wysłane przez Yin jest bardzo szybki. Na mojej maszynie jest to również około 0,5 sekundy. Jednakże, jeśli chcesz napisać proste rozwiązanie funkcjonalne można po prostu napisać to:

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 

To po prostu sprawdza, czy dana liczba jest liczbą pierwszą dla wszystkich liczb do 1 miliona. Nie używa żadnych wyrafinowanych algorytmów (to zabawne, że rozwiązanie, które jest najprostsze, często jest wystarczająco dobre!).Na moim komputerze twoja zaktualizowana wersja działa około 11 sekund, a to trwa około 2 sekund.

Co ciekawsze, bardzo łatwo jest zrównoleglić. Jeśli użyjesz PLINQ, możesz napisać poniższą wersję i będzie działać prawie 2 razy szybciej na dwurdzeniowym rdzeniu. Oznacza to, że na poczwórnym rdzeniu może być tak szybki, jak najszybsze rozwiązanie wszystkich odpowiedzi, ale przy minimalnym wysiłku programistycznym :-) (oczywiście, używając czterech rdzeni nie jest ekologiczny, ale .. dobrze)

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

Funkcje PSeq są owijkami dla PLINQ, które stworzyłem dla mojej książki (to sprawia, że ​​używanie PLINQ z F # jest bardziej naturalne). Są one dostępne w .

Answer 5

EDIT: zaktualizowana wersja poniżej, zużywa mniej pamięci i jest szybszy

Czasami dobrze jest móc mutować rzeczy. Oto, co prawda, raczej imperatywna wersja, która wymienia pamięć na szybkość. Ponieważ ten wątek okazał się być hostem ładnego zbioru funkcji generujących prime w F #, pomyślałem, że i tak byłoby miło dodać moje. Użycie funkcji BitArray powoduje, że sprawdzanie pamięci odbywa się w trybie ręcznym.

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:

Kod powyżej, można optymalizować dalej: gdy jest stosowana tylko nieparzyste indeksów w sitowej BitArray mogą być zmniejszone o połowę wielkości indeksując nieparzystą N jako 2M + 1. Nowa wersja jest również szybsze:

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 

rozrządu (Intel Core Duo 2.33GHz):

> 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