快速获得Eratosthenes的功能筛

本文介绍了快速获得Eratosthenes的功能筛的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我阅读了有关该算法的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,000th 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.)