haskell - Haskell --> F#: ターナーのふるい

Question

オイラーのふるいと呼ばれるエラトステネスのふるいの一種の改良版に出くわしたとき、私はさまざまなふるいアルゴリズムについて読んでいました。ウィキペディアによると、Haskell には少し異なるバージョンのアイデア (Turner's Sieve と呼ばれる) の実装があります。

今、私は与えられたコードスニペットが正確に何をするのかを理解しようとしています。私はそれを理解していると思いますが、今はコードを F# に変換したかったのですが、どこから始めればよいのか本当にわかりません。私の主な懸念は、2 つのシーケンスを「減算」する機能がないように見えることです。

コードは次のとおりです。

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計算内のすべてのリストが (遅延的に) 無限であることがわかっている場合でも、コンパイラが不完全な一致について文句を言わないようにするために、2 つの句を追加したことに注意してください。

score 2 · Accepted Answer

seqでそれを行うことができます。そして、あなたがやったように、euler自体は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

最初に、素数のオイラーのふるいは「エラトステネスのふるいの改良版」ではないということを言わなければなりません。あらゆる意味でのパフォーマンスは、エラトステネスのふるいのどのバージョンよりもはるかに悪いからです。素数アルゴリズムに関する Haskell Wiki -オイラー

次に、LazyList を使用した @cfem のコードは、上記のリンクに従って奇数のみをふるい分けするというわずかな改善が欠けていますが、あなたが提供したオイラーのふるいのバージョンの冗長ではあるが忠実な翻訳であると言わなければなりません。

オイラーふるいの実装には実際には何の意味もないことに注意する必要があります。これは、TDO (Trial Division Optimized) によって素数を見つけるよりも複雑で遅いため、見つかった素数による除算のみをの平方根まで行うためです。Haskell Wiki on Prime Number algorithm - 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 個の素数を約 2 秒で見つけることができます。

これで、オイラーふるいは奇数ふるいの最適化を行うことができ、次のように LazyList を使用して表現できます。入力リストのパラメーターが無限であり、比較一致が単純化されていることがわかっているため、1 つの一致ケースが削除され、演算子も追加されています。コードを読みやすくするための '^':

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))

ただし、1899 番目の素数 (16381) を計算する時間は、primesTDO と primesTDOS でそれぞれ約 0.2 秒と 0.16 秒であることに注意する必要があります。この小さな範囲でも 10 倍の時間です。ひどいパフォーマンスに加えて、primeE は 3000 までの素数を計算することさえできません。これは、見つかった素数の増加に伴い、遅延実行関数の数が急速に増加しているため、メモリ使用率がさらに悪化するためです。

LazyList は値であり、以前に見つかった要素の記憶が組み込まれているため、記述されたコードの繰り返しのタイミングに注意する必要があることに注意してください。タイミングのために、PrimeE を PrimeE() のように関数にして、作業が毎回最初から開始されるようにする方がよい場合があります。

要約すると、F# を含む任意の言語で実装されたオイラーふるいは、興味深い知的な演習にすぎず、合理的に最適化された他のほぼすべてのふるいよりもはるかに遅く、メモリを大量に消費するため、実用的ではありません。

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
    }

haskell - Haskell --> F#: ターナーのふるい

4 に答える 4

Related

Reference