Nachdem ich schon im Beitrag “Der Weg ist das Ziel” Code von Java nach Scala “übersetzt” habe, probiere ich es diesmal mit einer funktionalen Sprache, nämlich Haskell – nicht dass ich Haskell wirklich beherrschen würde, aber dafür reicht es gerade so.
Ausgangspunkt ist der wirklich lesenswerte Artikel The Genuine Sieve of Eratosthenes” von Melissa E. O’Neill, in dem sie aufzeigt, dass das, was vielen Informatik-Studenten als Sieb des Eratosthenes verkauft wird, gar nicht der originale Algorithmus – der mit dem Abstreichen – ist, sondern ein zwar kurzes und elegant wirkendes, dafür aber hoffnungslos ineffizientes Plagiat. Nun ist es trivial, den originalen Algorithmus zu implementieren, wenn man vorher weiß, bis zu welcher Schranke die Primzahlen berechnet werden sollen. Deshalb stellt die Autorin eine clevere Implementierung vor, die das Durchstreichen sozusagen “just in time” durchführt.
Setzen wir also die elaborierteste Version (zu finden auf Seite 7 und 8 des Papiers) nach Scala 2.8 um:
object primes {
type SI = Stream[Int]
def sieve:SI = {
def wheel2357:SI = Stream(4,2,4,6,2,6,4,2,4,6,6,
2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,
6,4,2,4,6,2,6,4,2,4,2,10,2,10,2) append wheel2357
def spin(s:SI, n:Int):SI = Stream.cons(n, spin(s.tail, n + s.head))
case class It(value:Int, step:Int) {
def next = new It(value + step, step)
def atLeast(c:Int):It =
if (value >= c) this
else new It(value + step, step).atLeast(c)
}
implicit object ItOrdering extends Ordering[It] {
def compare(thiz:It, that:It) = {
val r = thiz.value - that.value
if (r == 0) thiz.step - that.step else r
}
}
import scala.collection.immutable.TreeSet
def sieve(cand:SI, set:Set[It]):SI = {
val c = cand.head
val set1 = TreeSet[It]() ++ set.dropWhile(_.value < c) ++
set.takeWhile(_.value < c).map(_.atLeast(c))
if (set1.elements.next.value == c) {
val set2 = TreeSet[It]() ++ set1.dropWhile(_.value == c) ++
set1.takeWhile(_.value == c).map(_.next)
sieve(cand.tail, set2)
} else {
Stream.cons(c, sieve(cand.tail, set1 + It(c*c,2*c)))
}
}
Stream(2,3,5,7,11) append sieve(spin(wheel2357,13),
new TreeSet[It] + It(121,22))
}
def main(args:Array[String]) {
sieve.takeWhile(_ < 1000).foreach(println)
}
}
Dieser Code versucht, möglichst dicht am Original zu bleiben. Wie immer sieht der ganze Apparat viel furchterregender aus, als er eigentlich ist. Ich kann hier nur einen kurzen Überblick geben und empfehle, das sehr verständlich geschrieben Original-Papier zu lesen, bei dem die Ideen dieses Algorithmus Schritt für Schritt abgeleitet werden.
Die Zeile type SI = Stream[Int] führt einen Typ-Alias für Integer-Streams ein, denn wir benutzen sie hier wirklich oft, nämlich überall, wo in Haskell Listen verwendet wurden (die vom Verhalten her mehr mit Streams gemein haben als mit Scala-Listen). Wer genau hinschaut wird erkennen, dass das “Wheel” einen Schritt weiter gedreht ist als im Original – mehr dazu später. Das Wheel optimiert alle Kandidaten-Zahlen weg, die bereits durch 2, 3, 5 oder 7 teilbar sind. Dazu speichert es die Schrittweiten zum jeweis nächsten möglichen Kandidaten. So kann in der Methode spin() ganz einfach ein Stream erzeugt werden, der nur Zahlen mit größeren Primfaktoren als 2, 3, 5 und 7 enthält.
Nun kommt die Fallklasse It (für “Iterator”). Wenn wir eine neue Primzahl gefunden haben, erzeugen wir für diese ein neues It-Objekt, was dann später alle Vielfachen dieser Primzahl “just in time” eliminiert. Dazu werden bei jeder neuen Kandidatenzahl alle Its, die kleiner dieser Zahl sind, hochgesetzt. Gibt es danach mindestens ein It, das auf unserer Kandidatenzahl “landet”, ist diese zusammengesetzt. Wurde unser Kandidat dagegen von allen kleineren Its “übersprungen”, ist dieser eine neue Primzahl.
ItOrdering wird gebraucht, um die Its immer sortiert halten zu können. Als implizites Objekt muss man es nicht übergeben, sondern es fungiert als eine Art “Default” für alle “interessierten” Methoden oder Klassen (in unserem Fall TreeSet). Dazu müssen diese einen entsprechenden impliziten Parameter vereinbaren, der dann automatisch “gefüllt” wird – wobei es natürlich auch erlaubt ist, einen normalen Parameter mitzugeben, um ein anderes als das Standard-Verhalten zu erzwingen.
Im Original-Papier wird eine Priority-Queue verwendet. Auch Scala hat eine Implementierung, aber im Unterschied zur Haskell-Version ist diese veränderlich und unterstützt auch nicht das wahlfreie Löschen von Elementen. Als “Ersatz” muss deshalb hier ein TreeSet herhalten. In einer ernsthaften Implementierung würde man wahrscheinlich besser mit einer eigenen Implementierung fahren. Man sieht auch, dass das Hantieren mit dem TreeSet nicht besonders elegant aussieht und demnach eine “maßgeschneiderte” Lösung sehr zur Übersichtlichkeit beitragen könnte.
Am Ende wird ein wenig “Setup” betrieben und die innere sieve-Methode – das eigentliche Arbeitstier – gestartet. Dabei ist im Gegensatz zur Original-Version schon die Primzahl 11 (und ihr entsprechendes It-Objekt) vorhanden, weil der Umgang mit einem eventuell leeren Set umständliche Fallunterscheidungen erfordert hätte. Das ist auch der Grund, warum das Wheel bei 13 und nicht bei 11 beginnt.
Alles in allem war es eine sehr interessante Sache, Haskell-Code in Scala abzubilden, und auch wenn er jetzt nicht mehr ganz so elegant ist, kann man doch noch die Ausgangsversion recht gut wiedererkennen. Auf eine derartige Implementierung mit verschachtelten Streams wäre ich bestimmt nicht von allein gekommen.
Ich hoffe, dass dieser Beitrag nicht zu mathematisch geraten ist, und würde mich natürlich über Verbesserungsvorschläge freuen.
. 
