Scala, Erasthenes: Gibt es eine einfache Möglichkeit, einen Stream durch eine Iteration zu ersetzen?

In Ihrem ersten Code sollten Sie die Verschmelzung verschieben , bis das Quadrat einer Primzahl unter den Kandidaten gesehen wird. Dadurch wird die Anzahl der verwendeten Streams drastisch reduziert, was zu einer drastischen Verbesserung der Speicherbelegung führt. Um die 1000. Primzahl, 7919 , zu erhalten, müssen wir nur Primzahlen berücksichtigen, die nicht oberhalb ihrer Quadratwurzel liegen, 88 . Das sind nur 23 Primes / Streams ihrer Vielfachen, anstatt 999 ( 22 , wenn wir die Gleichungen von Anfang an ignorieren). Für die 10.000ste Primzahl ist es der Unterschied zwischen 9999 Strömen von Multiples und nur 66 . Und für den 100.000sten werden nur 189 benötigt.

Der Trick besteht darin, die verbrauchten Primzahlen von den erzeugten Primzahlen durch einen rekursiven Aufruf zu trennen:

Als zusätzlichen Bonus müssen die Primzahlquadrate nicht als Long s gespeichert werden. Dies wird auch viel schneller sein und eine bessere algorithmische Komplexität (Zeit und Raum) haben, da es viele überflüssige Arbeit vermeidet. Der Ideone-Test zeigt, dass er ungefähr bei < n ^1.5..1.6 empirische Wachstumsordnungen bei der Produktion von bis zu n = 80.000 Primzahlen.

Hier gibt es noch ein algorithmisches Problem: Die Struktur, die hier erzeugt wird, ist immer noch eine lineare, nach links gerichtete Struktur (((mults_of_2 + mults_of_3) + mults_of_5) + ...) , mit mehr produzierenden Strömen, die tiefer in ihm liegen (also haben die Zahlen mehr Ebenen, durch die man sickern kann) oben). Die rechte Struktur sollte besser sein, mults_of_2 + (mults_of_3 + (mults_of_5 + ...)) . Wenn man es zu einem Baum macht, sollte dies eine echte Verbesserung der zeitlichen Komplexität mit sich bringen (es wird typischerweise auf ~ n ^1.2..1.25 heruntergedrückt). Für eine verwandte Diskussion, siehe diese hakellwiki-Seite .

Das "echte" Imperativsieb von Eratosthenes läuft normalerweise um n 1.1 (in n erzeugten Primzahlen) und einer optimalen Probedivision Sieb bei ~ n ^1.40..1.45 . Ihr ursprünglicher Code wird um ungefähr in Kubik-Zeit oder schlechter wiedergegeben. Das imperativ veränderbare Array ist normalerweise das schnellste, das nach Segmenten arbeitet (ua das segmentierte Sieb von Eratosthenes).

Im Kontext Ihres zweiten Codes So wird es in Python erreicht .

Ich denke, es ist ein Fehler in der aktuellen Stream Implementierung.

primes().drop(999).head funktioniert gut:

Sie erhalten OutOfMemoryError mit gespeicherten Stream wie folgt:

Das Problem hier mit der Klasse Cons Implementierung : Es enthält nicht nur berechnet tail , sondern auch eine Funktion zur Berechnung dieser tail . Auch wenn tail berechnet wird und keine Funktion mehr benötigt wird!

In diesem Fall sind Funktionen extrem schwer, so dass Sie OutOfMemoryError auch bei 1000 gespeicherten Funktionen erhalten.

Wir müssen diese Funktionen irgendwie fallen lassen.

Intuitive Korrektur ist fehlgeschlagen:

Mit iterator auf Stream erhalten Sie StreamIterator , mit StreamIterator#toStream werden Sie get anfangs schwer Stream .

Abhilfe

Also müssen wir es manuell konvertieren:

  

Gibt es eine einfache Möglichkeit, den Code mit Streams in Iteratoren zu übersetzen? Oder gibt es eine einfache Möglichkeit, meinen ersten Versuch effizienter zu gestalten?

@Will Ness hat Ihnen eine verbesserte Antwort mit Streams gegeben und Gründe angegeben, warum Ihr Code so viel Speicher und Zeit benötigt wie beim frühen Hinzufügen von Streams und einer linksgerichteten linearen Struktur, aber niemand hat die zweite (oder vielleicht wichtigsten) Teil Ihrer Frage, wie ein echtes inkrementelles Sieb von Eratosthenes mit Iterator implementiert werden kann.

Zuerst sollten wir diesen rechtsgerichteten Algorithmus, von dem Ihr erster Code ein grobes (linkes) Beispiel ist (da er alle Prime-Composite-Streams den Merge-Operationen vorzeitig hinzufügt), die auf Richard Bird zurückzuführen ist, richtig gutschreiben im Epilog von Melissa E. O'Neills endgültiges Papier über inkrementelle Siebe von Eratosthenes .

Zweitens, nein, es ist nicht wirklich möglich, Iteratoren für Streams in diesem Algorithmus zu ersetzen, da es darauf ankommt, sich durch einen Stream zu bewegen, ohne den Stream neu zu starten, und obwohl man auf den Kopf eines Iterators zugreifen kann (die aktuelle Position), Wenn der nächste Wert (Überspringen des Kopfes) verwendet wird, um den Rest der Iteration als einen Stream zu erzeugen, muss ein vollständig neuer Iterator mit schrecklichen Kosten in Speicher und Zeit erstellt werden. Wir können jedoch einen Iterator verwenden, um die Ergebnisse der Sequenz von Primzahlen auszugeben, um die Speichernutzung zu minimieren und die Verwendung von Iterator-Funktionen höherer Ordnung zu erleichtern, wie Sie in meinem Code unten sehen werden.

Now Will Ness hat Sie durch die Prinzipien des Verschiebens von Prime-Composite-Streams zu den Berechnungen geführt, bis sie benötigt werden, was gut funktioniert, wenn Sie diese in einer Struktur wie einer Prioritätswarteschlange oder einer HashMap speichern und sogar übersehen wurden das O'Neill-Papier, aber für den Richard-Bird-Algorithmus ist dies nicht notwendig, da zukünftige Stream-Werte nicht erst aufgerufen werden, wenn sie benötigt werden, also nicht gespeichert werden, wenn die Streams richtig träge aufgebaut sind (wie träge und nach links). Tatsächlich benötigt dieser Algorithmus nicht einmal die Speicherung und die Gemeinkosten eines vollständigen Stroms, da sich jede zusammengesetzte Zahl-Culling-Sequenz nur ohne Bezug auf irgendwelche früheren Primzahlen vorwärts bewegt, außer wenn eine separate Quelle der Basis-Primzahlen benötigt wird, die geliefert werden können ein rekursiver Aufruf desselben Algorithmus.

Lassen Sie uns zur schnellen Referenz den Haskell-Code der Richard Bird-Algorithmen wie folgt auflisten:

Im folgenden Code habe ich die "Minus" -Funktion ("minusStrtAt") vereinfacht, da wir keinen komplett neuen Stream erstellen müssen, sondern die zusammengesetzte Subtraktion mit der Generierung des Originals kombinieren können (in meinem Fall) Quoten nur) Reihenfolge. Ich habe auch die "Union" -Funktion vereinfacht (umbenennen sie als "MrgMltpls")

Die Stream-Operationen werden als generischer Co Inductive Stream (CIS) implementiert, wobei das erste Feld der Klasse der Wert der aktuellen Position des Streams und das zweite Feld ein Thunk (ein Null-Argument) ist Funktion, die den nächsten Wert des Streams durch eingebettete Abschlussargumente an eine andere Funktion zurückgibt).

Der obige Code generiert die 100.000ste Primzahl (1299709) auf ideone in etwa 1,3 Sekunden mit einem Overhead von etwa 0,36 Sekunden und hat eine empirische Rechenkomplexität auf 600.000 Primzahlen von etwa 1,43. Der Speicherverbrauch ist gegenüber dem Programmcode vernachlässigbar.

Der obige Code könnte unter Verwendung der eingebauten Scala-Streams implementiert werden, aber es gibt einen Performance- und Speicherverbrauchs-Overhead (mit einem konstanten Faktor), den dieser Algorithmus nicht benötigt. Die Verwendung von Streams würde bedeuten, dass man sie direkt ohne den zusätzlichen Iterator-Generierungscode verwenden könnte, aber da dies nur für die endgültige Ausgabe der Sequenz verwendet wird, kostet es nicht viel.

Um eine einfache Baumfaltung zu implementieren, wie Will Ness vorgeschlagen hat, muss man nur eine "paar" -Funktion hinzufügen und sie in die Funktion "mrgMltpls" einbinden:

Der obige Code generiert die 100.000ste Primzahl (1299709) auf ideone in etwa 0,75 Sekunden mit einem Overhead von etwa 0,37 Sekunden und hat eine empirische Rechenkomplexität zur 1.000.000sten Primzahl (15485863) von etwa 1,09 (5,13 Sekunden). Der Speicherverbrauch ist gegenüber dem Programmcode vernachlässigbar.

Beachten Sie, dass die obigen Codes vollständig funktionsfähig sind, da kein veränderbarer Zustand verwendet wird, aber der Bird-Algorithmus (oder sogar die Baumfaltungsversion) nicht so schnell ist wie eine Prioritätswarteschlange oder HashMap für größere Bereiche Die Anzahl der Operationen zur Verarbeitung der Baumverschmelzung hat eine höhere Rechenkomplexität als der Log n-Overhead der Prioritätswarteschlange oder die lineare (amortisierte) Leistung einer HashMap (obwohl es einen großen konstanten Faktor-Overhead zur Handhabung des Hashing gibt, so dass der Vorteil nicht gegeben ist) 't wirklich gesehen, bis einige wirklich große Bereiche verwendet werden).

Der Grund dafür, dass diese Codes so wenig Speicher verwenden, besteht darin, dass die CIS-Ströme ohne permanenten Verweis auf den Anfang der Ströme formuliert werden, so dass die Ströme bei der Verwendung als Müll gesammelt werden und nur die minimale Anzahl der Basis-Primzahl übrig bleibt Sequenzplatzhalter, die, wie Will Ness erklärt hat, sehr klein sind - nur 546 Basenpaare mit zusammengesetzten Primzahlen für die Erzeugung der ersten Million Primzahlen bis zu 15485863, wobei jeder Platzhalter nur einige 10 Bytes (acht für die Lange Zahl, acht für die 64-Bit-Funktionsreferenz, mit einem weiteren Paar von acht Bytes für den Zeiger auf die Abschlussargumente und noch ein paar Bytes für Funktions- und Klassen-Overheads, für einen Gesamt-pro-stream-Platzhalter von vielleicht 40 Bytes oder insgesamt nicht viel mehr als 20 Kilobyte zum Erzeugen der Sequenz für eine Million Primzahlen).

Wenn Sie nur einen unendlichen Strom von Primzahlen wollen, ist dies meiner Meinung nach der eleganteste Weg: