Ich bin neu bei Haskell und versuche Eulers Sieb im Stream-Processing-Stil zu implementieren.
Als ich das Haskell-Wiki über Primzahlen überprüfte, fand ich eine mysteriöse Optimierungstechnik für Streams. In 3.8 Lineares Zusammenführen dieses Wikis:
%Vor%Und es sagt
" Der doppelte Primzahl-Feed wird hier eingeführt, um unnötige zu vermeiden Memorization und damit Speicherleck, wie Melissa O'Neill's Code. "
Wie könnte das sein? Ich kann nicht herausfinden, wie es funktioniert.
Normalerweise ist die Definition von Primzahlen in Richard Birds Formulierung des Siebs von Eratosthenes selbstreferentiell:
%Vor% Die durch diese Definition erzeugten Primzahlen ps werden als Eingabe verwendet. Um einen Teufelskreis zu verhindern, wird die Definition mit dem Anfangswert 2 initialisiert. Dies entspricht der mathematischen Definition des Siebs von Eratosthenes als Fundpunkte in den Lücken zwischen den Verbünden, aufgezählt für jede Primzahl p durch Aufzählen in Schritten von p , P = {2} U ({3,4, ...) } \ U {{ p 2 , p 2 + p , p 2 + 2p , ...} | p in P }).
Der erzeugte Stream wird als Eingabe in seiner eigenen Definition verwendet. Dies bewirkt, dass der gesamte Strom von Primzahlen im Speicher gehalten wird (oder das meiste davon sowieso). Der Fixpunkt ist hier sharing , corescursive :
%Vor%Die Idee (aufgrund von Melissa O'Neill) ist es dann, diese in zwei Streams zu unterteilen, mit einer inneren Schleife in den zweiten Strom von Primzahlen "über" es:
%Vor% Wenn also ps2 einige Primzahl p erzeugt, muss der innere Stream xs von "core" Primzahlen nur bis zu etwa sqrt p und Primzahlen, die das sind, instanziiert werden Produziert von ps2 kann unmittelbar danach von dem System verworfen und von Müll entsorgt werden:
Primes, die von der inneren Schleife xs erzeugt werden, können nicht sofort verworfen werden, da sie für xs stream selbst benötigt werden. Wenn xs ein primäres q erzeugt hat, kann nur sein Teil unterhalb von sqrt q verworfen werden, unmittelbar nachdem es vom foldr -Teil der Berechnung verbraucht wurde. Mit anderen Worten, diese Sequenz behält den Zeiger in sich zurück bis zum sqrt des größten produzierten Wertes (wie es von seinem Consumer konsumiert wird, wie print ).
Bei einer Feedschleife (mit fix ) müsste also fast die gesamte Sequenz im Speicher gehalten werden, während beim Double Feed (mit fix2 ) nur die innere Schleife beibehalten werden muss, die nur nach oben reicht zur Quadratwurzel des aktuellen Wertes, der vom Hauptstrom erzeugt wird. Somit ist die gesamte Raumkomplexität von etwa O (N) auf etwa O (sqrt (N)) reduziert - eine drastische Reduktion.
Damit dies funktioniert, muss der Code mit Optimierungen kompiliert werden, d. h. mit dem Schalter -O2 , und eigenständig ausgeführt werden. Möglicherweise müssen Sie auch -fno-cse switch verwenden. Und es darf nur einen Verweis auf ps2 im Testcode geben:
Tatsächlich zeigt einen praktisch konstanten Speicherverbrauch
Und es ist das Sieb von Eratosthenes, nicht Eulers Sieb.
Die anfänglichen Definitionen sind:
%Vor% Beide sind wegen der vorzeitigen Behandlung der Vielfachen sehr ineffizient. Es ist leicht, die erste Definition zu bereinigen, indem man die map und die Enumeration in eine weiter entfernte Enumeration fusioniert (von x nach x*x , dh [x*x, x*x+x..] ), so dass sie behandelt wird kann verschoben werden - weil hier die Vielfachen jeder Primzahl unabhängig voneinander erzeugt werden ( ):
ist das gleiche wie Birds Sieb oben in diesem Post, segmentweise :
%Vor% ( (f <*> g) x = f x (g x) wird hier als pointfree verwendet.)
Es gibt keine einfache Lösung für die zweite Definition, d. h. eulers .
Zusatz: Sie können dieselbe Idee sehen, die mit Python-Generatoren implementiert wurde, hier .
Tatsächlich verwendet dieser Python-Code eine teleskopische, mehrstufige rekursive Erzeugung von ephemeren Primes-Strömen; in Haskell können wir dies mit dem nicht-sharing, multi-staged Fixpoint-Kombinator _Y :
Tags und Links haskell primes lazy-sequences sieve-of-eratosthenes