Warum läuft der Sieve-Algorithmus in Scala so langsam?

Es gibt ein paar potentielle Probleme, obwohl ich nicht wirklich eine einzige "rauchende Waffe" sehe ... Wie auch immer, hier ist, was ich habe. Erstens:

könnte prägnanter geschrieben werden als:

Als Nächstes wird upper in filterPrimes nicht verwendet (dies sollte jedoch keine Auswirkung auf die Leistung haben).

Drittens: Verwenden Sie nicht eine var - und eine for -Schleife, wenn Sie wirklich einen reinen funktionalen Stil verwenden möchten, sondern filterPrimes in eine tailrekursive Funktion umwandeln. Der Compiler könnte schlau genug sein, um die Kopien zu optimieren, wenn Sie es so machen (obwohl ich nicht die Luft anhalten würde).

Schließlich und wahrscheinlich am wichtigsten ist, dass Ihre for -Schleife sehr viel Zeit verschwendet, um Werte herauszufiltern, die notwendigerweise bereits gefiltert wurden. Zum Beispiel wird versucht, Vielfache von 4 zu filtern, nachdem bereits alle Vielfachen von 2 gefiltert wurden. Wenn Sie diesen Siebalgorithmus effizient verwenden möchten, müssen Sie Ihre Startwerte aus den verbleibenden Elementen in der Liste auswählen.

Mit anderen Worten, behalten Sie einen Index in der Liste und bestimmen Sie den Seed aus dem Index, wie:

Dies vermeidet den doppelten Aufwand. Außerdem musst du nicht weiter iterieren, bis du zu max kommst. Ich denke, du kannst tatsächlich aufhören, wenn du an sqrt(max) vorbeikommst.

Wenn Sie eine funktionierende Art des Siebmachens sehen möchten, besuchen Sie The Echtes Sieb von Eratosthenes .

Ich würde ein paar Änderungen vornehmen.

• Es ist seltsam, dass Sie filterPrimes für alle Zahlen zwischen 2 und max / 2 ausführen. Bei der "tatsächlichen" Siebtechnik müssen Sie nur filterPrimes für alle Primzahlen ausführen zwischen 2 und sqrt(max) .
• Es erscheint auch seltsam, dass Sie eine var- und eine for-Schleife verwenden. Um es "funktional" zu machen, würde ich stattdessen eine rekursive Funktion verwenden.
• Anstatt filterPrimes für die gesamte Liste auszuführen, können Sie die Primzahlen auch während des gesamten Vorgangs sammeln. es ist nicht nötig, diese Filter immer wieder durch den Filter zu werfen.
• Es ist ziemlich seltsam für map und dann für filter , wie Sie es tun, da die Karte einfach kennzeichnet, welche Elemente gefiltert werden sollen. Sie können dasselbe auch nur mit Filter erreichen.

Also hier war mein erster Versuch diese Modifikationen:

Dies spiegelt jedoch meinen Haskell-Bias wider und hat einen großen Nachteil: Er wird aufgrund des rekursiven Aufrufs y :: go(...) in der go -Helfer-Funktion viel Platz im Stack beanspruchen. Das Ausführen von sieve(1000000) führte zu einem "OutOfMemoryError" für mich.

Versuchen wir einen üblichen FP-Trick: Tail-Rekursion mit Akkumulatoren.

Indem wir einen Akkumulatorwert hinzufügen, können wir die go Hilfsfunktion in tail-rekursive Form schreiben und somit das große Stack-Problem von früher vermeiden. (Haskells Auswertungsstrategie ist sehr unterschiedlich; sie benötigt weder Vorteile noch profitiert sie von der Tail-Rekursion)

Vergleichen wir nun die Geschwindigkeit mit einem imperativen, auf Mutationen basierenden Ansatz.

Hier verwende ich eine Array[Option[Int]] , und "cross off" eine Zahl durch Ersetzen seiner Eingabe mit "None". Es gibt ein kleines bisschen Raum für die Optimierung; vielleicht könnte eine kleine Geschwindigkeitsverstärkung erhalten werden, indem ein Array von Bools verwendet wird, wobei der Index die bestimmte Zahl darstellt. Was auch immer.

Unter Verwendung sehr primitiver Techinques (sorgfältig plazierte new Date() Aufrufe ...) habe ich die funktionale Version als ungefähr 6-mal langsamer verglichen als die imperative Version. Es ist klar, dass die beiden Ansätze die gleiche Groß-Oh-Zeit-Komplexität aufweisen, aber die konstanten Faktoren, die bei der Programmierung mit verknüpften Listen beteiligt sind, verursachen Kosten.

Ich habe auch Ihre Version mit Math.sqrt(max).ceil.toInt anstelle von max / 2 getestet. Sie war etwa 15x langsamer als die hier vorgestellte funktionale Version. Interessanterweise wird ¹ geschätzt, dass etwa 1 von 7 Zahlen zwischen 1 und 1000 ( sqrt(1000000) ) ist prime (1 / ln (1000)), daher kann ein großer Teil der Verlangsamung auf die Tatsache zurückgeführt werden, dass Sie die Schleife für jede einzelne Zahl ausführen, während ich meine Funktion nur für jede Funktion ausführe prime. Wenn es natürlich 15x so lange dauert, ~ 1000 Iterationen durchzuführen, würde 7500x so lange dauern, um 500000 Iterationen durchzuführen , weshalb der ursprüngliche Code quälend langsam ist.

Dies ist ein schnelles Sieb, das Hinweise auf Mergeconflict und einige Hinweise aus dem Papier, erwähnt von Ken Wayne VanderL, enthält:

Diagramm vergleichen: Die vertikale Achse zeigt Sekunden, die horizontale liegt zwischen 100 000 und 1 000 000 Primzahlen. Der deltaNovember-Algorithmus wurde bereits so verbessert, dass er nur noch nach math.sqrt (max) läuft, und die von Alexey Romanov im Kommentar vorgeschlagene Filterung. Von Dan Burton habe ich den zweiten Algorithmus und den letzten mit einer kleinen Modifikation genommen, um zu meiner Schnittstelle (List, nicht Array) und dem BitSet-Sieb zu passen, mit dem er nur in einem Kommentar verlinkt ist, aber der am schnellsten ist.

Listen sind unveränderlich und jeder Aufruf von filterPrimes erstellt eine neue Liste. Sie erstellen viele Listen, was übrigens unnötig ist.

Gehen Sie mit Ihrem ersten Instinkt (was Sie wahrscheinlich das "imperative equivalent" nennen), was ich vermute, verwendet ein single veränderbares Array.

(Bearbeitet, um klarzustellen, dass ich verstanden habe, dass die Erstellung mehrerer Listen unnötig war.)