optimization - 这个质数生成器的执行时间可以提高吗？

Question

我在写这篇文章时的最初目标是尽可能地留下最小的足迹。我可以自信地说，这个目标已经实现。不幸的是，这给我留下了一个相当缓慢的实现。要生成 200 万以下的所有素数，在 3Ghz 英特尔芯片上大约需要 8 秒。

有没有办法以最小的内存占用量来改善这段代码的执行时间？或者，从功能的角度来看，我是否以错误的方式处理这个问题？

代码

/// 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.5 秒而不是 8 秒。这是一个相当大的改进。

Answer 1

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.37 倍，而且它也非常接近最快的命令式版本的速度。我们可以让它更快，因为我们不需要过滤 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.530 秒下降到 01.364 秒，因此速度提高了大约 1.21 倍。惊人的!