Thời gian thực thi của bộ tạo số nguyên tố này có được cải thiện không?

Question

Mục tiêu ban đầu của tôi khi viết điều này là để lại dấu chân nhỏ nhất có thể. Tôi có thể nói với sự tự tin rằng mục tiêu này đã được đáp ứng. Thật không may, điều này lá tôi với một thực hiện khá chậm. Để tạo ra tất cả các số nguyên tố dưới 2 triệu, mất khoảng 8 giây trên chip Intel 3Ghz.

Có cách nào để cải thiện thời gian thực thi của mã này với sự hy sinh tối thiểu cho bộ nhớ nhỏ không? Ngoài ra, tôi đang đi về điều này một cách sai lầm khi nhìn vào nó từ một quan điểm chức năng?

MÃ

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

Cập nhật

tôi tinh chỉnh các thuật toán và quản lý để cạo 2 giây nhưng tiêu thụ bộ nhớ kép.

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

Cập nhật

Rõ ràng, tôi đã sử dụng một trình biên dịch cũ. Với phiên bản mới nhất, thuật toán gốc của tôi mất 6.5s thay vì 8 giây. Đó là một cải tiến khá.

Answer 1

Tomas Petricek's function là khá nhanh, nhưng chúng tôi có thể làm cho nó nhanh hơn một chút.

Hãy so sánh như sau:

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 có một chút hơi nhanh hơn vòng trong. Chiến lược tạo chiến lược nổi tiếng của nó sử dụng "chuyển đổi" để bỏ qua các số nguyên tố không theo số gia số là 2 hoặc 4. Để so sánh:

> 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 

Phiên bản của tôi nhanh hơn khoảng 2,37 lần và nó cũng khá gần với tốc độ của các phiên bản bắt buộc nhanh nhất. Chúng ta có thể làm cho nó thậm chí nhanh hơn vì chúng ta không cần phải lọc danh sách các 2L .. 2000000L, chúng ta có thể sử dụng cùng một chiến lược để tạo ra một chuỗi tối ưu hơn về số nguyên tố càng tốt trước khi chúng ta áp dụng bộ lọc của chúng tôi:

> 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 

chúng tôi giảm từ 1,530 xuống còn 1,36 giây, vì vậy chúng tôi đã tăng thêm khoảng 1,21 lần. Tuyệt vời!

Answer 2

Tôi đã viết một phiên bản cấp bách, nhanh hơn. Không thể viết Sieve of Eratosthenes theo cách chức năng thuần túy để đạt được cùng tốc độ vì bạn phải có trạng thái nhị phân cho mỗi số.

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

Chỉ để xem các trò vui, chúng ta hãy xem this page.

pi (x) là hàm đếm chính, nó trả về số lượng số nguyên tố bên dưới x. Bạn có thể xấp xỉ pi (x) bằng cách sử dụng bất đẳng thức sau:

(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) là chức năng chính của thứ n, mà có thể xấp xỉ bằng:

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

Với ý nghĩ đó, here is a very fast generator mà tính các số nguyên tố đầu tiên, trong đó mỗi phần tử tại chỉ số i bằng p(i). Vì vậy, nếu chúng tôi muốn giới hạn mảng của chúng tôi với số nguyên tố dưới 2.000.000, chúng tôi sử dụng chênh lệch trên cho hàm đếm chính:

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! Vậy nhanh đến mức nào? Trên 3.2GHz quad-core của tôi, tôi nhận được sau trong 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 

Vì vậy, đó là tất cả các số nguyên tố xung quanh 2 triệu trong vòng chưa đầy nửa giây :)

Answer 4

Phiên bản bắt buộc đăng bởi Yin là rất Nhanh. Trên máy của tôi, nó cũng khoảng 0,5 giây. Tuy nhiên, nếu bạn muốn viết một giải pháp đơn giản mà bạn chỉ có thể viết những dòng này:

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 

này chỉ đơn giản là kiểm tra xem một số là số nguyên tố cho tất cả các số tới 1 milion. Nó không sử dụng bất kỳ thuật toán phức tạp nào (nó thực sự buồn cười là một giải pháp đơn giản nhất thường đủ tốt!).Trên máy tính của tôi, phiên bản cập nhật của bạn chạy khoảng 11 giây và điều này chạy khoảng 2 giây.

Thú vị hơn, điều này rất dễ dàng để song song. Nếu bạn sử dụng PLINQ, bạn có thể viết phiên bản dưới đây và nó sẽ chạy nhanh hơn gấp 2 lần trên lõi kép. Điều này có nghĩa là trên lõi tứ, nó có thể nhanh như giải pháp nhanh nhất từ ​​tất cả các câu trả lời ở đây, nhưng với nỗ lực lập trình tối thiểu :-) (tất nhiên, sử dụng 4 lõi không sinh thái, nhưng .. tốt)

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

Chức năng PSeq là trình bao bọc cho PLINQ mà tôi đã tạo cho sách của mình (nó làm cho việc sử dụng PLINQ từ F # tự nhiên hơn). Chúng có sẵn trong .

Answer 5

EDIT: cập nhật phiên bản dưới đây, sử dụng ít bộ nhớ và vận hành nhanh

Đôi khi nó tốt đến mức khó có thể đột biến thứ. Đây là một phiên bản được thừa nhận, thay vì bắt buộc, giao dịch bộ nhớ cho tốc độ. Kể từ khi thread này bật ra để lưu trữ một bộ sưu tập tốt đẹp của các chức năng tạo ra nguyên tố trong F #, tôi nghĩ rằng nó sẽ được tốt đẹp để thêm tôi anyway. Sử dụng một BitArray giúp giữ lại bộ nhớ trong kiểm tra.

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 

Cập nhật:

Đoạn mã trên có thể được tối ưu hóa hơn nữa: vì nó chỉ sử dụng các chỉ số lẻ trong rây, các BitArray có thể được giảm xuống còn một nửa kích thước bằng cách lập chỉ mục lẻ n như 2m + 1. Phiên bản mới cũng là nhanh hơn:

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.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