|
|
Kleine Sachen mit PythonDas Sieb des Eratosthenes |
|
|
Der schönen Schlichtheit wegen
|
Auf meinen Seiten zur Programmiersprache Ada habe ich das Sieb des alten Herren Eratosthenes bereits mit großem Getöse ausgeschlachtet, um nach einem alten Rezept Primzahlen zu 'gewinnen', deshalb sei hier in Demut eine kleine rekursive Lösung vorgestellt, mit zwei Listen und Python, und ganz ohne Getöse. |
|
|
Die funktionale Programmiersprache Haskell erlaubt das Arbeiten mit unendlichen Listen und kennt die bedarfsgesteuerte Auswertung von Ausdrücken (lazy evaluation). Die wundersame Haskell-Funktion primzahlen kommt daher ohne die Angabe einer Obergrenze aus:
primzahlen = sieb [2 ..] und berechnet vom Algorithmus her alle Primzahlen - alle bis der Rechner schlapp macht, bis des Rechners Speicher ausgeschöpft ist. Erst dachte ich, die Generator-Ausdrücke aus dem Sprachvorrat von Python könnten mir helfen, quasi grenzenlos zu arbeiten. Aber ich musste bei meinen Versuchen doch immer eine Obergrenze angeben. - Python ist groß, Haskell ist noch großartiger. Allein schon: Der Ausdruck x:xs zerlegt eine Liste sehr anschaulich in Kopf und den Rest, prägnanter geht es kaum. Allerdings ist Haskell unbarmherzig rein funktional angelegt; wenn ein Problem nun doch danach schreit, einen Zustand im Gedächtnis halten zu wollen - wie es bei einem Zustandsautomaten oder bei der Ein- und Ausgabe zwangsläufig der Fall ist - dann bedarf es dazu solcher Konstrukte wie die der Monaden; was an sich eine spannende Angelegenheit ist, woran aber nicht jeder gemeine Programmierer im Kampf mit seinen Brot- und Butterproblemen Gefallen finden wird. Also doch der Griff im Alltag zu dem wunderbaren Python, damit geht eben schlicht Vieles. Genau das erfreut mich. Da war doch noch etwas? Ja, auch Haskell kennzeichnet Blöcke durch Einrückungen - ist dem weißen Raum verfallen. Python hat diesen syntaktischen weißen Raum von Haskell übernommen (- las ich irgendwo). Nun denn, ich spendiere einfach, da wo der Quellcode ob des weißen Raumes allzusehr auseinander fällt, Kommentare der Art # end if, Lady Ada Lovelace lässt grüßen. |
Des großartigen Aufwands wegen
|
Warum denn mit der Triangel nur ein leises 'Kling' machen, wenn es auch mit der großen Pauke geht. Mein Thema ist Python und threads, ich nenne threads einfach Ablauffäden. Es geht mir natürlich nicht um das Problem der Gewinnung von Primzahlen an sich, ich möchte vielmehr ein Modell aufstellen und dieses Modell mit Pythons Sprachmitteln ausformulieren. Mit Ada hatte ich ja schon zum Thema Primzahlen mächtig Quellcode aufgetürmt. Nun ist Python dran ... Mein Modell für Sieb des Eratosthenes ist: Primzahlen werden durch aktive Objekte modelliert, die durch Brücken zum Zahlentransport verbunden sind. Erhält ein Primzahlobjekt nun eine Zahl, so überprüft das Objekt, ob die eingegangene Zahl durch seine Primzahl teilbar ist, wenn das der Fall ist, liegt keine Primzahl vor - die eingegangene Zahl ist keine Primzahl -, andernfalls wird die Zahl zum nächsten Primzahlobjekt geschickt, gegebenenfalls wird ein neues Primzahlobjekt mit einer Verbindungsbrücke erzeugt. Im Einzelnen: Ich betrachte hier nur ungerade Zahlen und fange mit der wohlbekannten Primzahl 3 an, die bereits durch ein aktives Objekt modelliert sein soll. Als nächste Zahl erhält das Primzahlobjekt '3' die Zahl 5, die nicht durch 3 (und nicht durch 2) teilbar ist, also eine neue Primzahl ist - die Nachfolger-Primzahl der 3. Das Primzahl-Objekt '3' erzeugt nun ein neues Objekt '5' für die neue Primzahl und eine Brücke, die sie und das neue Objekt verbindet. Alle Zahlen, die nicht durch 3 teilbar sind, werden diesem Nachfolger-Objekt zur Überprüfung zugeschickt, alle durch 3 teilbaren Zahlen werden herausgefiltert - gesiebt - und werden nicht weitergereicht. Das Fünfer-Objekt erzeugt dann das Siebener-Objekt, das das Elfer-Objekt und so fort. Dieses so anschauliche Modell lässt sich direkt in Python-Code umsetzen: Primzahl-Objekte werden durch aktive threads dargestellt, als Brücken werden Warteschlangen, queues, verwendet. Oder anders formuliert: Primzahl-Objekte sind Objekte der Klasse PrimeWorker. Beim Anlegen eines solchen Objektes werden diesem die zu verwaltende Primzahl number und eine Funktion getNextNumber übergeben; mithilfe dieser Funktion holt sich das Objekt beim Vorgänger die nächste zu überprüfende Zahl ab. Zudem wird bereits eine Warteschlange MyQueue bereitgestellt - die Brücke zum Nachfolger des neuerzeugten Objekts, dieser Nachfolger wird erst später angelegt werden. Die Aktionen, die die Objekte zyklisch ausführen sollen, sind in der Funktion run aufgeführt. Zunächst werden solange Zahlen vom Vorgänger abgeholt, bis die erste neue Primzahl erkannt wird; trifft die Zahl 0 ein, dient sie als Ende-Kriterium, das Objekt und der Ablauffaden haben seine Schuldigkeit getan. |
 |
|
Die neue Primzahl wird in eine Ergebnisliste primeNumbers eingefüttert, wobei die elegante with-Anweisung den Zugriff auf die Liste schützt. Und es wird im Fluge und noch innerhalb der Klasse primeWorker ein neues primeWorker-Objekt nextWorker für die Primzahl erzeugt und auch gleich gestartet. Und es funktioniert - gegen meine Erwartung, die immer noch durch die rigide Sprache Ada genährt wird. Ich bin entzückt über die Einfachheit, mit der mit Sprache Python gesprochen werden kann. Da steht im Quellcode kein Deut mehr als gemacht werden soll. Anschließend wird weiter gesiebt (Zahlen, die keine Primzahlen sind, werden verworfen) oder aber es werden Primzahl-Kandidaten durch die Warteschlange zum vormals erzeugten Nachfolger zur weiteren Überprüfung geschickt. Eine weitere Klasse firstWorker spendiert ein Singleton-Objekt, das das erste primeWorker-Objekt erzeugt und die sich aufbauende Kette von primeWorker-Objekten mit Zahlen füttert.
Hier nun die Primzahl-Zwillinge bis zur Zahl 10000:
# Beginning ... Die Laufzeiten einschließlich des mitlaufenden Profilers schwanken um einige Sekunden, sie betragen 8,559 Sekunden oder auch 9,775 Sekunden, 10,566 Sekunden, 7,005 Sekunden. Wo kommen die großen Laufzeitunterschiede bloß her?, denn eine ressourcenfressende Anwendung lief nicht nebenher.)
Der weitaus größte Teil der Ablaufzeit scheint für die Verwaltung
der Ablauffäden aufgewendet zu werden - wenn ich dem Profiler
glauben schenken darf, wenn ich ihn überhaupt richtig verstehe.
Nun denn, meine Umsetzung des Siebalgorithmus
hier ist ja auch mehr eine akademische Übung als
auf die praktische Anwendung ausgerichtet:
python -m cProfile sieve-11-profile.py
...
14694 function calls in 7.005 seconds
ncalls tottime filename:lineno(function)
...
1237 6.97 {method acquire of _thread.lock objects}
...
Der Python-Interpreter bricht jedenfalls unter
der Last der Ablauffäden nicht so schnell
zusammen, nach einigen Sekunden mehr hat er auch die
Primzahlen bis 30000 bestimmt, mit
nicht wenigen, genau mit immerhin 3245 Primzahl-Threads:
# Enter a 'number' > 2 OR 'e' for exit ... N> 30000 # Largest number is: 30000 > Number of primes: 3245 > Number of twins: 467 Die Einschränkung bei Python: Die Ablauffäden (threads) sind nicht mehrkern-fähig. Es wird in der Dokumentaion empfohlen, dann schwergewichtigere Prozesse zu verwenden. - Die Bequemlichkeit, die eine interpretierte Programmiersprache für den Software-Entwickler bietet, hat halt auch ihren Preis. Zwei Zitate aus der Python-Dokumentation (Python 3.4.2):
GIT - global interpreter lock |
Quellcode für Python 3
|
|
||
| © 2015 Bernd Ragutt Alle Rechte vorbehalten |
|
letzte Änderung: 17. März 2018 Kruschtkiste |
|
|
||