performance - 快速获得Eratosthenes的功能筛

我读了this other post about a F# version of this algorithm。我发现它非常优雅，并试图结合一些答案的想法。

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

所以我的问题是，我是否缺少使这一切变得如此缓慢的东西。例如，在another post中，有人推测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))

最佳答案

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

关于performance - 快速获得Eratosthenes的功能筛，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6469982/