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

问题描述

我写这篇文章时的最初目标是尽可能减少占用空间.我可以自信地说，这个目标已经实现.不幸的是，这给我留下了一个相当缓慢的实现.要生成 200 万以下的所有质数，在 3Ghz 英特尔芯片上大约需要 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.5 秒而不是 8 秒.这是一个相当大的进步.

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 的函数 非常快，但我们可以让它更快一点.

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.530 秒下降到 01.364 秒，因此速度提高了大约 1.21 倍.太棒了！

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

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