在F#中找到素数很慢

Question

我在C中使用了Eratosthenes的Sieve非常容易地回答了Project Euler Question 7,我没有遇到任何问题.

我对F#还是很陌生,所以我尝试实现相同的技术

let prime_at pos =
  let rec loop f l =
    match f with 
    | x::xs -> loop xs (l |> List.filter(fun i -> i % x <> 0 || i = x))
    | _ -> l

  List.nth (loop [2..pos] [2..pos*pos]) (pos-1)

当pos <1000时效果很好,但在内存不足的情况下会在10000时崩溃

然后我尝试将算法更改为

let isPrime n = n > 1 && seq { for f in [2..n/2] do yield f } |> Seq.forall(fun i -> n % i <> 0)

seq {for i in 2..(10000 * 10000) do if isPrime i then yield i} |> Seq.nth 10000 |> Dump

哪个成功运行但仍需要几分钟.

如果我理解正确,第一个算法是尾部优化的,为什么它会崩溃？我怎样才能编写一个运行时间不到1分钟的算法(我有一台快速计算机)？

Answer 1

看着你的第一次尝试

let prime_at pos =
  let rec loop f l =
    match f with 
    | x::xs -> loop xs (l |> List.filter(fun i -> i % x <> 0 || i = x))
    | _ -> l

  List.nth (loop [2..pos] [2..pos*pos]) (pos-1)

在每次循环迭代中,您将迭代并创建新列表.这非常慢,因为列表创建速度非常慢,并且您没有看到缓存带来的任何好处.跳过了几个明显的优化,例如跳过偶数的因子列表.当pos=10 000您尝试创建一个仅占10 000 * 10 000 * 4 = 400MB用整数和更多800MB指针的列表时(F#列表是链接列表).此外,由于每个列表元素占用的内存非常少,因此GC开销可能会带来很大的开销.在该功能中,您可以创建一个新的熟悉大小的列表.因此,我对此并不感到惊讶OutOfMemoryException.

看第二个例子,

let isPrime n = 
    n > 1 && 
    seq { for f in [2..n/2] do yield f } 
    |> Seq.forall(fun i -> n % i <> 0)

在这里,问题非常相似,因为您正在为您正在测试的每个元素生成巨型列表.

我在这里写了一个非常快的F#筛子/sf/answers/841043591/,它展示了如何更快地完成这项工作.