haskell - Haskell --> F#：特纳的筛子

Question

当我偶然发现一种称为欧拉筛的改进版的埃拉托色尼筛时，我正在阅读不同的筛分算法。根据Wikipedia，在 Haskell 中有一个稍微不同版本的想法（称为 Turner's Sieve）的实现。

现在我试图了解给出的代码片段到底是做什么的，我想我已经明白了，但现在我想将代码翻译成 F# 并且真的不知道从哪里开始。我主要担心的是似乎没有“减去”两个序列的功能。

这是代码：

import Data.OrdList (minus)

primes = euler [2..]
euler (p : xs) = p : euler (xs `minus` map (*p) (p : xs))

这将如何在 F# 中实现？甚至可能吗？

score 9 · Accepted Answer

如果你想像 Haskell 那样计算无限列表的合并/差异，那么 LazyList 类型（在 F# 电源包中找到）就会浮现在脑海中。

它产生了非常冗长的代码，如下面的翻译：

#r "FSharp.PowerPack.dll"

//A lazy stream of numbers, starting from x
let rec numsFrom x = LazyList.consDelayed x (fun () -> numsFrom (x+1))

//subtracts L2 from L1, where L1 and L2 are both sorted(!) lazy lists
let rec lazyDiff L1 L2 =
    match L1,L2 with
        | LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1<x2 ->
            LazyList.consDelayed x1 (fun () -> lazyDiff xs1 L2)
        | LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1=x2 ->
            lazyDiff xs1 L2
        | LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1>x2 ->
            lazyDiff L1 xs2
        | _ -> failwith "Should not occur with infinite lists!"

let rec euler = function
    | LazyList.Cons(p,xs) as LL ->
        let remaining = lazyDiff xs (LazyList.map ((*) p) LL)
        LazyList.consDelayed p (fun () -> euler remaining)
    | _ -> failwith "Should be unpossible with infinite lists!"

let primes = euler (numsFrom 2)

和

> primes |> Seq.take 15 |> Seq.toList;;
val it : int list = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47]

请注意，我添加了两个failwith子句以防止编译器抱怨不完全匹配，即使我们知道计算中的所有列表都是（懒惰的）无限的。

score 2 · Accepted Answer

你可以用seq来做。当你完成减号时，欧拉本身与 Haskell 中的相同。

let rec minus xs ys =
  seq {
    match Seq.isEmpty xs, Seq.isEmpty ys with
    | true,_ | _,true -> yield! xs
    | _ ->
       let x,y = Seq.head xs, Seq.head ys
       let xs',ys' = Seq.skip 1 xs, Seq.skip 1 ys
       match compare x y with
       | 0 -> yield! minus xs' ys'
       | 1 -> yield! minus xs ys'
       | _ -> yield x; yield! minus xs' ys
  }

let rec euler s =
  seq {
    let p = Seq.head s
    yield p
    yield! minus (Seq.skip 1 s) (Seq.map ((*) p) s) |> euler
  }

let primes = Seq.initInfinite ((+) 2) |> euler

score 2 · Accepted Answer

使用序列，您可以通过保持序列获得更多的竞争力：

let rec euler s =
    seq {
        let s = Seq.cache s
        let p = Seq.head s
        yield p
        yield! minus (Seq.skip 1 s) (Seq.map ((*) p) s) |> euler
    }

score 2 · Accepted Answer

首先，必须说欧拉的素数筛不是“埃拉托色尼筛的改进版本”，因为它在各个方面的性能都比任何版本的埃拉托色尼筛差得多：关于素数算法的 Haskell Wiki -欧拉

接下来，应该说@cfem 使用 LazyList 的代码是您提供的欧拉筛版本的忠实但冗长的翻译，尽管它缺乏根据上面的链接仅筛选奇数的轻微改进。

应该注意的是，实施欧拉筛实际上没有任何意义，因为它比通过试除法优化 (TDO) 找到素数更复杂和更慢，因为它只通过找到的素数进行除法，直到平方根为素数测试的候选数： Haskell Wiki on Prime Number algorithms - TDO。

这个Trial Division Optimized (TDO) 筛子可以使用 LazyList（参考 FSharp.PowerPack.dll）在 F# 中实现，如下所示：

let primesTDO() =
  let rec oddprimes =
    let rec oddprimesFrom n =
      if oddprimes |> Seq.takeWhile (fun p -> p * p <= n) |> Seq.forall (fun p -> (n % p) <> 0)
      then LazyList.consDelayed n (fun() -> oddprimesFrom (n + 2))
      else oddprimesFrom (n + 2)
    LazyList.consDelayed 3 (fun() -> oddprimesFrom 5)
  LazyList.consDelayed 2 (fun () -> oddprimes)

它可以使用与以下相同形式的序列来实现：

let primesTDOS() =
  let rec oddprimes =
    let rec oddprimesFrom n =
      if oddprimes |> Seq.takeWhile (fun p -> p * p <= n) |> Seq.forall (fun p -> (n % p) <> 0)
      then seq { yield n; yield! oddprimesFrom (n + 2) }
      else oddprimesFrom (n + 2)
    seq { yield 3; yield! (oddprimesFrom 5) } |> Seq.cache
  seq { yield 2; yield! oddprimes }

序列版本比 LazyList 版本稍快，因为它避免了调用时的一些开销，因为 LazyList 是基于缓存的序列。两者都使用一个内部对象，该对象表示到目前为止找到的素数的缓存副本，在 LazyList 的情况下自动缓存，在序列的情况下由 Seq.cache 缓存。任何一个都可以在大约两秒内找到前 100,000 个素数。

现在，欧拉筛可以进行奇数筛分优化，并使用 LazyList 表示如下，由于知道输入列表参数是无限的并且比较匹配被简化，因此消除了一个匹配情况，以及我添加了一个运算符'^' 使代码更具可读性：

let primesE = //uses LazyList's from referenced FSharp.PowerPack.dll version 4.0.0.1
  let inline (^) a ll = LazyList.cons a (LazyList.delayed ll) //a consd function for readability
  let rec eulers xs =
    //subtracts ys from xs, where xs and ys are both sorted(!) infinite lazy lists
    let rec (-) xs ys =
      let x,xs',ys' = LazyList.head xs,LazyList.tail xs,LazyList.tail ys
      match compare x ( LazyList.head ys) with
        | 0 -> xs' - ys' // x == y
        | 1 -> xs - ys' // x > y
        | _ -> x^(fun()->(xs' - ys)) // must be x < y
    let p = LazyList.head xs
    p^(fun() -> (((LazyList.tail xs) - (LazyList.map ((*) p) xs)) |> eulers))
  let rec everyothernumFrom x = x^(fun() -> (everyothernumFrom (x + 2)))
  2^(fun() -> ((everyothernumFrom 3) |> eulers))

但是，必须注意的是，对于 primesTDO 和 primesTDOS，计算第 1899 个素数（16381）的时间分别约为 0.2 和 0.16 秒，而使用这个 primesE 大约需要 2.5 秒，因为欧拉筛在 over即使对于这个小范围，时间也是十倍。除了糟糕的性能外，primeE 甚至无法计算到 3000 的素数，因为它的内存利用率更差，因为它记录了数量迅速增加的延迟执行函数，并随着找到的素数的增加而增加。

请注意，在重复编写代码时必须小心，因为 LazyList 是一个值，并且具有对先前找到的元素的内置记忆，因此第二次相同的扫描将花费接近零的时间；出于计时目的，最好将 PrimeE 设置为 PrimeE() 中的函数，这样每次工作都从头开始。

总之，用包括 F# 在内的任何语言实现的欧拉筛只是一个有趣的智力练习，并没有实际用途，因为它比几乎所有其他合理优化的筛都慢得多，而且占用的内存也差得多。

haskell - Haskell --> F#：特纳的筛子

4 回答 4

Related

Reference