Haskell -> F #: Turner Sieve

Question

Ich las auf verschiedenen Sieben Algorithmen, wenn ich auf eine Art eine verbesserte Version des Sieb des Eratosthenes stolperte Eulers genannt Sieve. Nach Wikipedia gibt es eine Implementierung von eine etwas andere Version der Idee in Haskell (Turner-Sieve genannt).

Jetzt versuche ich zu verstehen, was genau die Code-Snippet gegeben hat, und ich glaube, ich habe es aber jetzt wollte ich den Code in F # übersetzen und habe wirklich keine Ahnung, wo ich anfangen soll. Meine größte Sorge ist, dass es keine Funktion zu „subtrahieren“ zwei Sequenzen zu sein scheint.

Hier ist der Code:

import Data.OrdList (minus)

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

Wie würde sich dies in F # umgesetzt werden? Ist es überhaupt möglich?

Answer 1

Wenn Sie Dinge wie Merges / Unterschiede der unendlichen Listen berechnen wie Haskell tut, der LazyList Typ in dem Sinne (im Innern des F # Netzteils gefunden).

Es macht für sehr ausführlichen Code, wie die Übersetzung unter:

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

mit

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

Beachten Sie, dass ich zwei failwith Klauseln hinzugefügt, um die Compiler zu halten von etwa einem unvollständigen Spiel beschweren, auch wenn wir wissen, dass alle Listen in der Berechnung sind (träge) unendlich.

Answer 2

Sie können es mit f . Und wie Sie bekam minus gemacht, euler selbst ist die gleiche wie in 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

Answer 3

Mit Sequenzen, Sie viel mehr wettbewerbsfähig erhalten, indem die Sequenz persistierenden:

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
    }

Answer 4

Zuerst muss man sagen, dass das Sieb Euler für Primzahlen ist keine „verbesserte Version des Siebs des Eratosthenes“, wie seine Leistung in jeder Hinsicht ist viel schlimmer als jede Version des Siebs des Eratosthenes: Haskell Wiki auf Prime Number Algorithmen - Euler

Als nächstes sollte man sagen, dass @ CFEM den Code LazyList der ist eine originalgetreue obwohl die ausführliche Übersetzung der Version des Siebes Eulers, dass Sie gab, obwohl es die leichte Verbesserung von nur Sieben ungerade Zahlen gemäß den obigen Link fehlt.

Es ist zu beachten, dass es nicht wirklich jeder Punkt in das Euler-Sieb Implementierung, da es komplexe und langsamer als Primzahlen durch Verfahrensabteilung Optimized zu finden (TDO), um nur durch gefunden Primzahlen bis zu dem Platz Division tun Wurzel der Kandidatenzahl für die Prime getestet gemäß: Haskell Wiki auf Prime Number Algorithmen - TDO .

Das Testabteilung Optimized (TDO) Sieb in F # mit LazyList des implementiert werden (mit einem Verweis auf FSharp.PowerPack.dll) als:

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)

Es kann als unter Verwendung von Sequenzen in der gleichen Form umgesetzt werden:

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 }

Die Sequenz-Version ist etwas schneller als die LazyList Version, da es einigen Aufwand in Aufruf durch vermeidet seit LazyList des basiert auf im Cache-Sequenzen. Beide verwenden ein internes Objekt, das eine zwischengespeicherte Kopie der Primzahlen darstellt bisher gefunden, automatisch im Fall von LazyList des zwischengespeichert und durch den Seq.cache im Fall von Sequenzen. Entweder können die ersten 100.000 Primzahlen in etwa zwei Sekunden finden.

Nun wird die Euler Sieb können die ungerade Zahl Sieben Optimierung haben und mit LazyList ist wie folgt ausgedrückt werden, mit einem Match Fall eliminiert aufgrund zu wissen, dass die Eingangsliste Parameter sind unendlich und der Vergleich Spiel vereinfacht, aber auch ich habe einen Operator ‚^‘ hinzugefügt den Code besser lesbar zu machen:

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

Es muss jedoch angemerkt werden, dass die Zeit, die 1899. prime zu berechnen (16381) sind etwa 0,2 und 0,16 Sekunden für die primesTDO und primesTDOS sind, während es etwa 2,5 Sekunden wird unter Verwendung dieses primesE für eine schreckliche Leistung für die Euler Sieb der Zeit, auch für diesen kleinen Bereich auf mehr als das zehn~~POS=TRUNC. Neben schreckliche Leistung, primeE kann nicht einmal berechnen Primzahlen bis 3000 aufgrund tun noch schlimmer Speichernutzung, da es eine schnell wachsende Zahl von latenten Ausführungsfunktionen mit zunehmender gefunden Primzahlen aufzeichnet.

Beachten Sie, dass man in wiederholtem Timing des Codes muß vorsichtig sein, wie geschrieben, da der LazyList ein Wert ist und verfügt über eine integrierte in dem Auswendiglernen von zuvor Elementen gefunden, so dass eine zweite identische Abtastung nahe Null Zeit in Anspruch nehmen; für Timing Zwecke könnte es besser sein, die PrimeE eine Funktion als in PrimeE (), so dass die Arbeit beginnt am Anfang jeder Zeit zu machen.

Insgesamt Sieb die Euler in jeder Sprache, einschließlich F # implementiert ist nur eine interessante intellektuelle Übung und hat keinen praktischen Nutzen, da es viel langsamer und Schweine Speicher viel schlimmer, als fast jeder andere vernünftig optimierte Sieb ist.