该素数生成器的执行时间可以提高吗？

我写这篇文章的最初目标是留下最小的空间。我可以放心地说，这个目标已经实现。不幸的是，这让我的执行速度很慢。要生成200万以下的所有素数，在3Ghz英特尔芯片上需要大约8秒。该素数生成器的执行时间可以提高吗？

有没有办法提高这段代码的执行时间，而对内存占用很小？另外，从功能的角度来看，我是从错误的角度来看待这个问题的吗？

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

更新

我调整的算法和管理，以刮掉2秒但双内存消耗。

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

更新

很显然，我是用一个旧的编译器。使用最新版本，我的原始算法需要6.5s而不是8s。这是一个很大的改进。

来源

2010-01-13 ChaosPandion

Tomas Petricek's function速度相当快，但我们可以让它快一点。

比较如下：

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有一个稍微快一点内环。它它采用了“切换”跳过2或4增量非素数比较知名的发电黄金策略：

> 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

我的版本是约2.37x较快，而其也八九不离十以最快的势在必行的版本的速度。我们可以把它更快因为我们并不需要过滤的2L .. 2000000L列表中，我们可以使用相同的策略来产生可能的素数更优化的序列，我们应用我们的过滤器之前：

> 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

我们从1.530s降至01.364s，因此我们获得了约1.21倍的速度。真棒！

来源

2010-01-13 06:02:22 Juliet

只是为了完整性，这里有一些与素数相关的函数：http://pastebin.com/f23c064c – Juliet 2010-01-13 07:04:43

现在，这真是太棒了！ – ChaosPandion 2010-01-13 20:52:58

我写了一个命令式的版本，速度更快。由于每个数字都必须有一个二进制状态，因此可能不可能用纯粹的函数式方式编写Eratosthenes的Sieve以达到相同的速度。

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

来源

2010-01-13 02:36:47

感谢张贴此，我喜欢看到其他国家的人民的算法。我也希望你错了，这是不可能的。 – ChaosPandion 2010-01-13 03:06:27

只是为了方便，让我们来看看this page。

pi（x）是素数计数函数，它返回低于x的素数数目。

(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）是第n个的首要功能，可使用近似：

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

考虑到这一点，here is a very fast generator其计算可以使用下面的不等式逼近圆周率（X）前n个素数，其中索引为i的每个元素等于p(i)。所以，如果我们要盖下面2000000我们的素数排列，我们使用上界不等式的主要计数功能：

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

酷！那么它有多快？在我的3.2GHz的四核，我得到了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

所以这是约200万的所有素数在不到半秒:)

来源

2010-01-13 03:34:36 Juliet

发表阴当务之急版本很快速。在我的机器上它也是大约0.5秒。然而，如果你想要写一个简单实用的解决方案，你可以只写：

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

这只是测试一个数是否是所有数字质数的1畅想。它不使用任何复杂的算法（实际上，最简单的解决方案通常足够好！在我的机器上，更新后的版本运行约11秒，运行时间约为2秒。

更有趣的是，这很容易并行化。如果你使用PLINQ，你可以编写下面的版本，在双核上运行速度将提高近2倍。这意味着在四核上，它可以像所有答案一样快，但是只需很少的编程工作:-)（当然，使用四个核心不是生态的，但是...）

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

PSeq函数是我为我的书创建的PLINQ的包装器（它使得使用F＃中的PLINQ更自然）。它们可在中获得。

来源

2010-01-13 03:51:57

我不得不把这个给朱丽叶做这些优化。我会买你的书作为安慰奖。 :) – ChaosPandion 2010-01-13 20:55:10

编辑：下面的更新版本，使用更少的内存和更快

有时它是很好的能够变异的东西。这是一个毫无疑问是非常必要的版本，它以速度换取记忆。由于这个线程原来在F＃中主持了一个很好的主要生成函数集合，所以我认为无论如何都要添加我的代码会很好。使用BitArray可以检查内存占用情况。

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

更新：

上面的代码可以进一步被优化：通过索引奇数n的2米，因为它仅使用奇数索引在筛中，BitArray可以减少到一半大小+ 1。新版本也快：

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

时序（英特尔酷睿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

来源

2010-01-13 08:28:56 cfern

该素数生成器的执行时间可以提高吗？

回答

相关问题