3

IE，

我在这里做错了什么？它是否与列表、序列和数组以及限制的工作方式有关？

所以这里是设置：我正在尝试生成一些素数。我看到有十亿个素数的十亿个文本文件。问题不在于为什么……问题是使用 python 的人如何在这篇文章中以毫秒为单位计算所有低于 1,000,000 的素数……我在下面的 F# 代码中做错了什么？

let sieve_primes2 top_number = 
    let numbers = [ for i in 2 .. top_number do yield i ]
    let sieve (n:int list) = 
        match n with
        | [x] -> x,[]
        | hd :: tl -> hd, List.choose(fun x -> if x%hd = 0 then None else Some(x)) tl
        | _ -> failwith "Pernicious list error."
    let rec sieve_prime (p:int list) (n:int list) =  
        match (sieve n) with
        | i,[] -> i::p
        | i,n'  -> sieve_prime (i::p) n'
    sieve_prime [1;0] numbers

在 FSI 中打开计时器后，我为 100000 获得了 4.33 秒的 CPU 时间……之后，一切都崩溃了。

4

4 回答 4

5

您的筛子功能很慢，因为您试图过滤掉高达top_number. 使用埃拉托色尼筛法，您只需要这样做，直到sqrt(top_number)剩余的数字本质上是素数。假设我们有top_number = 1,000,000，您的函数会78498进行几轮过滤（直到 的素数数1,000,000），而原始筛子只执行168几次（直到 的素数数1,000）。

您可以避免生成除 2 之外的偶数，因为 2 从一开始就不能是素数。而且，sieve和sieve_prime可以合并成一个递归函数。你可以使用轻量级List.filter而不是List.choose.

结合以上建议：

let sieve_primes top_number = 
    let numbers = [ yield 2
                    for i in 3..2..top_number -> i ]
    let rec sieve ns = 
        match ns with
        | [] -> []
        | x::xs when x*x > top_number -> ns
        | x::xs -> x::sieve (List.filter(fun y -> y%x <> 0) xs)
    sieve numbers

在我的机器上，更新版本非常快，在 0.6 秒内完成top_number = 1,000,000.

于 2012-08-17T23:58:25.037 回答
4

基于我的代码：stackoverflow.com/a/8371684/124259

在 fsi 中在 22 毫秒内获取前 100 万个素数 - 此时可能正在编译代码。

#time "on"

let limit = 1000000
//returns an array of all the primes up to limit
let table =
    let table = Array.create limit true //use bools in the table to save on memory
    let tlimit = int (sqrt (float limit)) //max test no for table, ints should be fine
    let mutable curfactor = 1;
    while curfactor < tlimit-2 do
        curfactor <- curfactor+2
        if table.[curfactor]  then //simple optimisation
            let mutable v = curfactor*2
            while v < limit do
                table.[v] <- false
                v <- v + curfactor
    let out = Array.create (100000) 0 //this needs to be greater than pi(limit)
    let mutable idx = 1
    out.[0]<-2
    let mutable curx=1
    while curx < limit-2 do
        curx <- curx + 2
        if table.[curx] then
            out.[idx]<-curx
            idx <- idx+1
    out
于 2012-08-18T00:54:42.893 回答
2

对于使用列表 (@pad) 的一般试验除法算法和使用埃拉托色尼筛 (SoE) (@John Palmer 和 @Jon Harrop) 选择用于筛选数据结构的数组，已经有几个很好的答案。但是，@pad 的列表算法并不是特别快，并且对于更大的筛选范围会“炸毁”，而@John Palmer 的数组解决方案稍微复杂一些，使用的内存比必要的多，并且使用外部可变状态，因此与程序是用 C# 等命令式语言编写的。

EDIT_ADD： 我编辑了下面的代码（带有行注释的旧代码）修改序列表达式以避免一些函数调用，以反映更多的“迭代器样式”，虽然它节省了 20% 的速度，但它仍然没有接近真正的 C# 迭代器，其速度与“滚动您自己的枚举器”最终 F# 代码的速度大致相同。我已经相应地修改了下面的时间信息。 END_EDIT

以下真正的 SoE 程序仅使用 64 KB 的内存来筛选多达一百万的素数（由于仅考虑奇数并使用压缩位 BitArray），并且仍然几乎与 @John Palmer 的程序一样快，大约需要 40 毫秒来筛选i7 2700K (3.5 GHz) 上一百万，只有几行代码：

open System.Collections
let primesSoE top_number=
  let BFLMT = int((top_number-3u)/2u) in let buf = BitArray(BFLMT+1,true)
  let SQRTLMT = (int(sqrt (double top_number))-3)/2
  let rec cullp i p = if i <= BFLMT then (buf.[i] <- false; cullp (i+p) p)
  for i = 0 to SQRTLMT do if buf.[i] then let p = i+i+3 in cullp (p*(i+1)+i) p
  seq { for i = -1 to BFLMT do if i<0 then yield 2u
                               elif buf.[i] then yield uint32(3+i+i) }
//  seq { yield 2u; yield! seq { 0..BFLMT } |> Seq.filter (fun i->buf.[i])
//                                          |> Seq.map (fun i->uint32 (i+i+3)) }
primesSOE 1000000u |> Seq.length;;

由于序列运行时库的低效率以及在每个函数调用大约 28 个时钟周期并以大约 16 个函数调用返回的成本，几乎所有经过的时间都花费在最后两行枚举找到的素数上每次迭代。通过滚动我们自己的迭代器，这可以减少到每次迭代只有几个函数调用，但代码并不那么简洁；请注意，在以下代码中，除了筛选数组的内容和使用对象表达式的迭代器实现所必需的引用变量之外，没有暴露可变状态：

open System
open System.Collections
open System.Collections.Generic
let primesSoE top_number=
  let BFLMT = int((top_number-3u)/2u) in let buf = BitArray(BFLMT+1,true)
  let SQRTLMT = (int(sqrt (double top_number))-3)/2
  let rec cullp i p = if i <= BFLMT then (buf.[i] <- false; cullp (i+p) p)
  for i = 0 to SQRTLMT do if buf.[i] then let p = i+i+3 in cullp (p*(i+1)+i) p
  let nmrtr() =
    let i = ref -2
    let rec nxti() = i:=!i+1;if !i<=BFLMT && not buf.[!i] then nxti() else !i<=BFLMT
    let inline curr() = if !i<0 then (if !i= -1 then 2u else failwith "Enumeration not started!!!")
                        else let v = uint32 !i in v+v+3u
    { new IEnumerator<_> with
        member this.Current = curr()
      interface IEnumerator with
        member this.Current = box (curr())
        member this.MoveNext() = if !i< -1 then i:=!i+1;true else nxti()
        member this.Reset() = failwith "IEnumerator.Reset() not implemented!!!"
      interface IDisposable with
        member this.Dispose() = () }
  { new IEnumerable<_> with
      member this.GetEnumerator() = nmrtr()
    interface IEnumerable with
      member this.GetEnumerator() = nmrtr() :> IEnumerator }
primesSOE 1000000u |> Seq.length;;

上面的代码在同一台机器上将素数筛选到一百万需要大约 8.5 毫秒，因为每次迭代的函数调用数量从大约 16 个大大减少到大约 3 个。这与以相同风格编写的 C# 代码的速度大致相同. 太糟糕了，我在第一个示例中使用的 F# 的迭代器样式不会像 C# 迭代器那样自动生成 IEnumerable 样板代码，但我想这就是序列的意图——只是它们在加速性能方面效率太低了由于被实现为序列计算表达式。

现在，只有不到一半的时间用于枚举主要结果，以便更好地利用 CPU 时间。

于 2013-08-03T17:52:36.930 回答
1

我在这里做错了什么？

您已经实现了一种不同的算法，该算法遍历每个可能的值并用于%确定是否需要将其删除。您应该做的是逐步通过固定增量删除倍数。那将是渐近的。

您无法有效地单步执行列表，因为它们不支持随机访问，因此请使用数组。

于 2013-02-10T21:02:58.503 回答