Haskell - F #: Turners Sieb

Wenn Sie Dinge wie Merges / Unterschiede von unendlichen Listen wie Haskell berechnen möchten, fällt Ihnen der LazyList-Typ (im F # -Power-Pack) ein.

Es macht sehr ausführlichen Code, wie die folgende Übersetzung:

mit

Beachten Sie, dass ich zwei failwith -Klauseln hinzugefügt habe, damit sich der Compiler nicht über eine unvollständige Übereinstimmung beschwert, selbst wenn wir wissen, dass alle Listen in der Berechnung (träge) unendlich sind.

Sie können es mit seq machen. Und wenn du minus fertig hast, ist euler selbst dasselbe wie in Haskell.

Mit Sequenzen werden Sie viel wettbewerbsfähiger, indem Sie die Sequenz beibehalten:

Zuerst muss man sagen, dass das Euler-Sieb für Primzahlen keine "verbesserte Version des Sievers von Eratosthenes" ist, da seine Leistung in jeder Hinsicht viel schlechter ist als jede Version des Sievers von Eratosthenes: Haskell Wiki auf Primzahlalgorithmen - Euler

Als nächstes sollte gesagt werden, dass @ cfems Code, der LazyList verwendet, eine getreue, wenn auch ausführliche Übersetzung der Version von Eulers Sieb ist, die Sie gegeben haben, obwohl es die leichte Verbesserung nur der ungeraden Zahlen wie oben beschrieben nicht enthält. p>

Es sollte angemerkt werden, dass es keinen Sinn hat, das Euler-Sieb zu implementieren, da es komplexer und langsamer ist als das Finden von Primzahlen durch Trial Division Optimized (TDO), um nur Divisionen durch gefundene Primzahlen bis zum Quadrat zu machen Wurzel der Kandidatennummer für Prime getestet nach: Haskell Wiki auf Primzahl-Algorithmen - TDO .

Dieses Trial Division Optimized (TDO) -Sieb kann in F # unter Verwendung von LazyLists (mit einem Verweis auf FSharp.PowerPack.dll) wie folgt implementiert werden:

Es kann mit Sequenzen in der gleichen Form implementiert werden wie:

Die Sequenzversion ist etwas schneller als die LazyList-Version, weil dadurch ein gewisser Mehraufwand beim Aufruf vermieden wird, da LazyLists auf zwischengespeicherten Sequenzen basieren. Beide verwenden ein internes Objekt, das eine zwischengespeicherte Kopie der bisher gefundenen Primzahlen darstellt, die im Falle von LazyLists automatisch zwischengespeichert wird, und im Fall von Sequenzen durch Seq.cache. Entweder können die ersten 100.000 Primzahlen in etwa zwei Sekunden gefunden werden.

Nun kann das Euler-Sieb die Optimierung der ungeraden Anzahl von Sieben haben und unter Verwendung von LazyLists wie folgt ausgedrückt werden, wobei ein Match-Fall aufgrund der Tatsache, dass die Parameter der Eingabeliste unendlich sind und der Vergleich übereinstimmt, eliminiert wird vereinfacht, außerdem habe ich einen Operator '^' hinzugefügt, um den Code lesbarer zu machen:

Es ist jedoch anzumerken, dass die Zeit für die Berechnung der 1899. Primzahl (16381) etwa 0,2 und 0,16 Sekunden für die PrimesTDO bzw. PrimesTDOS beträgt, während es bei dieser Primzahl etwa 2,5 Sekunden für eine für die Euler schreckliche Leistung ist Sieb über zehn Mal die Zeit sogar für diesen kleinen Bereich. Zusätzlich zu der schrecklichen Leistung kann primeE nicht einmal Primzahlen bis 3000 berechnen, da es eine noch schlechtere Speicherauslastung verursacht, da es eine schnell zunehmende Anzahl von verzögerten Ausführungsfunktionen mit zunehmenden gefundenen Primzahlen aufzeichnet.

Beachten Sie, dass man beim wiederholten Timing des Codes, wie er geschrieben wurde, vorsichtig sein muss, da die LazyList ein Wert ist und eine eingebaute Speicherung von zuvor gefundenen Elementen aufweist, so dass ein zweiter identischer Scan nahezu Null Zeit benötigt; Für Timing-Zwecke könnte es besser sein, das PrimeE zu einer Funktion wie in PrimeE () zu machen, so dass die Arbeit jedes Mal von Anfang an beginnt.

Zusammenfassend ist das Euler-Sieb, das in jeder Sprache einschließlich F # implementiert ist, nur eine interessante intellektuelle Übung und hat keinen praktischen Nutzen, da es viel langsamer ist und das Gedächtnis viel schlechter speichert als jedes andere vernünftig optimierte Sieb.