快速获得Eratosthenes的功能筛 [英] Getting functional sieve of Eratosthenes fast

问题描述

我阅读了有关该算法的F#版本的另一篇文章.我觉得它很优雅，并尝试结合一些答案的想法.

I read this other post about a F# version of this algorithm. I found it very elegant and tried to combine some ideas of the answers.

尽管我对其进行了优化，以减少检查次数(仅检查6左右的数字)，并且省去了不必要的缓存，但它仍然非常缓慢.计算第10,000 个素数已经花费了超过5分钟的时间.使用命令式方法，我可以在不多的时间内测试所有31位整数的情况.

Although I optimized it to make fewer checks (check only numbers around 6) and leave out unnecessary caching, it is still painfully slow. Calculating the 10,000^th prime already take more than 5 minutes. Using the imperative approach, I can test all 31-bit integers in not that much more time.

所以我的问题是我是否缺少使这一切变得如此缓慢的东西.例如，在另一篇帖子中，有人推测LazyList可能使用锁定.有人有主意吗?

So my question is if I am missing something that makes all this so slow. For example in another post someone was speculating that LazyList may use locking. Does anyone have an idea?

由于StackOverflow的规则说不发布新问题作为答案，因此我觉得必须为此开始一个新主题.

As StackOverflow's rules say not to post new questions as answers, I feel I have to start a new topic for this.

这是代码:

#r "FSharp.PowerPack.dll"

open Microsoft.FSharp.Collections

let squareLimit = System.Int32.MaxValue |> float32 |> sqrt |> int

let around6 = LazyList.unfold (fun (candidate, (plus, next)) -> 
        if candidate > System.Int32.MaxValue - plus then
            None
        else
            Some(candidate, (candidate + plus, (next, plus)))
    ) (5, (2, 4))

let (|SeqCons|SeqNil|) s =
    if Seq.isEmpty s then SeqNil
    else SeqCons(Seq.head s, Seq.skip 1 s)

let rec lazyDifference l1 l2 =
    if Seq.isEmpty l2 then l1 else
    match l1, l2 with
    | LazyList.Cons(x, xs), SeqCons(y, ys) ->
        if x < y then
            LazyList.consDelayed x (fun () -> lazyDifference xs l2)
        elif x = y then
            lazyDifference xs ys
        else
            lazyDifference l1 ys
    | _ -> LazyList.empty

let lazyPrimes =
    let rec loop = function
        | LazyList.Cons(p, xs) as ll ->
            if p > squareLimit then
                ll
            else
                let increment = p <<< 1
                let square = p * p
                let remaining = lazyDifference xs {square..increment..System.Int32.MaxValue}
                LazyList.consDelayed p (fun () -> loop remaining)
        | _ -> LazyList.empty
    loop (LazyList.cons 2 (LazyList.cons 3 around6))

推荐答案

如果您在任何地方调用Seq.skip，那么您有大约99％的机会拥有O(N ^ 2)算法.对于几乎所有涉及序列的优雅的功能懒惰Project Euler解决方案，您都想使用LazyList，而不是Seq. (有关更多讨论，请参见朱丽叶的评论链接.)

If you are calling Seq.skip anywhere, then there's about a 99% chance that you have an O(N^2) algorithm. For nearly every elegant functional lazy Project Euler solution involving sequences, you want to use LazyList, not Seq. (See Juliet's comment link for more discussion.)

这篇关于快速获得Eratosthenes的功能筛的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！