5

我阅读了有关该算法的 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))
4

2 回答 2

2

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

于 2011-06-24T15:48:06.387 回答
0

即使您成功解决了奇怪的二次 F# 序列设计问题，仍有一定的算法改进。你在(...((x-a)-b)-...)这里工作得很好。x, 或around6, 越来越深，但它是最频繁产生的序列。将其转换为(x-(a+b+...))方案 - 甚至在那里使用树结构 - 以提高时间复杂度（抱歉，该页面在 Haskell 中）。这实际上非常接近命令式筛选的复杂性，尽管仍然比基线 C++ 代码慢。

将局部经验增长顺序测量为O(n^a) <--> a = log(t_2/t_1) / log(n_2/n_1)（在n产生的素数中），理想n log(n) log(log(n))转化为范围内的O(n^1.12) .. O(n^1.085)行为n=10^5..10^7。一个简单的 C++ 基线命令式代码实现了O(n^1.45 .. 1.18 .. 1.14)树合并代码以及基于优先级队列的代码，O(n^1.20)或多或少都表现出稳定的行为。当然，C++ 的速度要快50 20..15倍，但这主要只是一个“常数因素”。:)

于 2012-01-01T01:45:05.913 回答