这个质数生成器的执行时间可以缩短吗? [英] Can the execution time of this prime number generator be improved?

问题描述

编写此书时，我的最初目标是尽可能地减少占用空间.我可以满怀信心地说这个目标已经实现.不幸的是，这使我执行起来很慢.要生成低于200万的所有素数，在3Ghz Intel芯片上大约需要8秒钟.

My initial goal when writing this was to leave the smallest footprint possible. I can say with confidence that this goal has been met. Unfortunately, this leaves me with a rather slow implementation. To generate all primes below 2 million it takes about 8 seconds on a 3Ghz Intel chip.

是否总要以最小的内存占用量来减少此代码的执行时间?另外，从功能的角度来看，这是我做错了吗?

Is there anyway to improve the execution time of this code with minimal sacrifice to the small memory footprint? Alternatively, am I going about this the wrong way when looking at it from a functional standpoint?

代码

/// 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秒的时间，但内存消耗却翻了一番.

I tweaked the algorithm and managed to shave off 2 seconds but double memory consumption.

/// 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.这是一个很大的进步.

Apparently, I was using an old compiler. With the latest version my original algorithm takes 6.5s rather than 8s. That is quite an improvement.

推荐答案

Tomas Petricek's function is pretty fast, but we can make it a little faster.

比较以下内容:

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的增量跳过非素数.为进行比较:

is_prime_juliet has a little slightly faster inner loop. Its a well-known prime-generating strategy which uses a "toggle" to skip non-primes in increments of 2 or 4. For comparison:

> 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.37倍，并且也与最快的命令式版本的速度非常接近.我们可以使它更快，因为我们不需要过滤2L .. 2000000L的列表，我们可以在应用过滤器之前使用相同的策略来生成更优化的可能素数序列:

My version is about 2.37x faster, and its also pretty close to the speed of the fastest imperative versions. We can make it even faster because we don't need to filter the list of 2L .. 2000000L, we can use the same strategy to generate a more optimal sequence of possible primes before we apply our filter:

> 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倍.太棒了！

We dropped from 1.530s to 01.364s, so we gained about 1.21x more speed. Awesome!

这篇关于这个质数生成器的执行时间可以缩短吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！