快速获得Eratosthenes的功能筛选

Question

我读了这篇关于这个算法的F#版本的帖子.我发现它非常优雅,并试图结合一些答案的想法.

虽然我对它进行了优化以减少检查(仅检查6左右的数字)并省去不必要的缓存,但仍然很慢.计算10,000 ^次素数已经超过5分钟.使用命令式方法,我可以在更长的时间内测试所有31位整数.

所以我的问题是,如果我遗漏了使这一切变得如此缓慢的事情.例如,在另一篇文章中有人猜测LazyList可能会使用锁定.有没有人有想法？

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

这是代码:

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

Answer 1

如果您在任何地方调用Seq.skip，那么您有大约 99% 的机会使用 O(N^2) 算法。对于几乎每个涉及序列的优雅函数惰性 Project Euler 解决方案，您想要使用LazyList，而不是Seq。（有关更多讨论，请参阅朱丽叶的评论链接。）