Kleine Sachen mit Python

Das Sieb des Eratosthenes




Der schönen Schlichtheit wegen


Auf meinen Seiten zur Pro­grammier­sprache Ada habe ich das Sieb des alten Herren Eratos­thenes bereits mit großem Getöse ausge­schlachtet, um nach einem alten Rezept Prim­zahlen zu 'gewin­nen', deshalb sei hier in Demut eine kleine rekur­sive Lösung vorge­stellt, mit zwei Listen und Python, und ganz ohne Getöse.

 

 

Die funktionale Programmier­sprache Haskell erlaubt das Arbeiten mit unend­lichen Listen und kennt die bedarfs­gesteuerte Aus­wertung von Aus­drücken (lazy evaluation). Die wunder­same Haskell-Funktion primzahlen kommt daher ohne die Angabe einer Ober­grenze aus:

      primzahlen = sieb [2 ..]
         where sieb (x:xs) = x:sieb [n | n<-xs, mod n x >0]

und berechnet vom Algo­rithmus her alle Primzahlen - alle bis der Rechner schlapp macht, bis des Rechners Speicher ausge­schöpft ist. Erst dachte ich, die Gene­rator-Aus­drücke aus dem Sprach­vorrat von Python könn­ten mir helfen, quasi grenzen­los zu arbeiten. Aber ich musste bei meinen Versuchen doch immer eine Ober­grenze angeben. - Python ist groß, Haskell ist noch groß­artiger. Allein schon: Der Ausdruck x:xs zerlegt eine Liste sehr anschau­lich in Kopf und den Rest, präg­nanter geht es kaum. Allerdings ist Haskell unbarm­herzig rein funk­tional angelegt; wenn ein Problem nun doch danach schreit, einen Zustand im Gedächt­nis halten zu wollen - wie es bei einem Zustands­auto­maten oder bei der Ein- und Ausgabe zwangs­läufig der Fall ist - dann bedarf es dazu solcher Kon­strukte wie die der Mo­naden; was an sich eine span­nende Angele­genheit ist, woran aber nicht jeder gemeine Program­mierer im Kampf mit seinen Brot- und Butter­problemen Gefallen finden wird. Also doch der Griff im Alltag zu dem wunder­baren Python, damit geht eben schlicht Vieles. Genau das erfreut mich.

Da war doch noch etwas? Ja, auch Haskell kenn­zeichnet Blöcke durch Einrü­ckungen - ist dem weißen Raum verfallen. Python hat diesen syntak­tischen weißen Raum von Haskell über­nommen (- las ich irgend­wo). Nun denn, ich spen­diere einfach, da wo der Quell­code ob des weißen Raumes all­zusehr ausein­ander fällt, Kommen­tare der Art # end if, Lady Ada Love­lace 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ür­lich nicht um das Problem der Gewin­nung von Prim­zahlen an sich, ich möchte vielmehr ein Modell auf­stellen und dieses Modell mit Pythons Sprach­mitteln ausformu­lieren. Mit Ada hatte ich ja schon zum Thema Prim­zahlen mächtig Quell­code aufge­türmt. Nun ist Python dran ...

Mein Modell für Sieb des Eratos­thenes ist: Prim­zahlen werden durch aktive Objekte model­liert, die durch Brücken zum Zahlen­transport verbun­den sind. Erhält ein Prim­zahl­objekt nun eine Zahl, so über­prüft das Objekt, ob die einge­gan­gene Zahl durch seine Primzahl teilbar ist, wenn das der Fall ist, liegt keine Prim­zahl vor - die einge­gangene Zahl ist keine Prim­zahl -, andern­falls wird die Zahl zum näch­sten Prim­zahl­objekt geschickt, gege­benen­falls wird ein neues Prim­zahl­objekt mit einer Verbin­dungs­brücke erzeugt.

Im Einzelnen: Ich betrachte hier nur ungerade Zahlen und fange mit der wohlbe­kannten Prim­zahl 3 an, die bereits durch ein aktives Objekt modelliert sein soll. Als nächste Zahl erhält das Prim­zahl­objekt '3' die Zahl 5, die nicht durch 3 (und nicht durch 2) teilbar ist, also eine neue Prim­zahl ist - die Nach­folger-Prim­zahl der 3.

Das Primzahl-Objekt '3' erzeugt nun ein neues Objekt '5' für die neue Prim­zahl und eine Brücke, die sie und das neue Objekt verbin­det. Alle Zahlen, die nicht durch 3 teil­bar sind, werden diesem Nach­folger-Objekt zur Über­prüfung zuge­schickt, alle durch 3 teil­baren Zahlen werden heraus­gefiltert - gesiebt - und werden nicht weiter­gereicht. Das Fünfer-Objekt erzeugt dann das Sie­bener-Objekt, das das Elfer-Objekt und so fort.

Dieses so anschau­liche Modell lässt sich direkt in Python-Code um­setzen: Prim­zahl-Objekte werden durch aktive threads darge­stellt, als Brücken werden Warte­schlangen, queues, verwendet.

Oder anders formuliert: Primzahl-Objekte sind Objekte der Klasse Prime­Worker. Beim Anlegen eines solchen Objektes werden diesem die zu verwaltende Prim­zahl number und eine Funktion getNextNumber über­geben; mit­hilfe dieser Funktion holt sich das Objekt beim Vor­gänger die nächste zu über­prüfende Zahl ab. Zudem wird bereits eine Warte­schlange MyQueue bereit­gestellt - die Brücke zum Nach­folger des neuer­zeugten Objekts, dieser Nach­folger wird erst später ange­legt werden.

Die Aktionen, die die Objekte zyklisch aus­führen sollen, sind in der Funk­tion run aufge­führt. Zu­nächst werden solange Zahlen vom Vor­gänger abge­holt, bis die erste neue Prim­zahl erkannt wird; trifft die Zahl 0 ein, dient sie als Ende-Krite­rium, das Objekt und der Ablauf­faden haben seine Schul­dig­keit getan.

 

 

Die neue Primzahl wird in eine Ergebnis­liste prime­Numbers einge­füttert, wobei die elegante with-Anwei­sung den Zugriff auf die Liste schützt. Und es wird im Fluge und noch inner­halb der Klasse prime­Worker ein neues primeWorker-Objekt next­Worker für die Prim­zahl erzeugt und auch gleich gestartet. Und es funktio­niert - gegen meine Erwar­tung, die immer noch durch die rigide Sprache Ada genährt wird. Ich bin entzückt über die Ein­fach­heit, mit der mit Spra­che Python gespro­chen werden kann. Da steht im Quell­code kein Deut mehr als gemacht wer­den soll.

Anschließend wird weiter gesiebt (Zahlen, die keine Prim­zahlen sind, werden ver­wor­fen) oder aber es werden Prim­zahl-Kandi­daten durch die Warte­schlange zum vor­mals erzeug­ten Nach­folger zur weite­ren Über­prü­fung geschickt.

Eine weitere Klasse firstWorker spendiert ein Singleton-Objekt, das das erste prime­Worker-Objekt erzeugt und die sich aufbau­ende Kette von prime­Worker-Objekten mit Zahlen füttert.

Hier nun die Primzahl-Zwil­linge bis zur Zahl 10000:

# Beginning ...
# Enter the largest 'number' for sieving ...
N> 10000
# Largest number is: 10000

> Number of primes: 1229
> Number of twins: 205

> The prime twins are:
[(3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (59,61), (71,73), (101,103), (107,109), (137,139), (149,151), (179,181), (191,193), (197,199), (227,229), (239,241), (269,271), (281,283), (311,313), (347,349), (419,421), (431,433), (461,463), (521,523), (569,571), (599,601), (617,619), (641,643), (659,661), (809,811), (821,823), (827,829), (857,859), (881,883), (1019,1021), (1031,1033), (1049,1051), (1061,1063), (1091,1093), (1151,1153), (1229,1231), (1277,1279), (1289,1291), (1301,1303), (1319,1321), (1427,1429), (1451,1453), (1481,1483), (1487,1489), (1607,1609), (1619,1621), (1667,1669), (1697,1699), (1721,1723), (1787,1789), (1871,1873), (1877,1879), (1931,1933), (1949,1951), (1997,1999), (2027,2029), (2081,2083), (2087,2089), (2111,2113), (2129,2131), (2141,2143), (2237,2239), (2267,2269), (2309,2311), (2339,2341), (2381,2383), (2549,2551), (2591,2593), (2657,2659), (2687,2689), (2711,2713), (2729,2731), (2789,2791), (2801,2803), (2969,2971), (2999,3001), (3119,3121), (3167,3169), (3251,3253), (3257,3259), (3299,3301), (3329,3331), (3359,3361), (3371,3373), (3389,3391), (3461,3463), (3467,3469), (3527,3529), (3539,3541), (3557,3559), (3581,3583), (3671,3673), (3767,3769), (3821,3823), (3851,3853), (3917,3919), (3929,3931), (4001,4003), (4019,4021), (4049,4051), (4091,4093), (4127,4129), (4157,4159), (4217,4219), (4229,4231), (4241,4243), (4259,4261), (4271,4273), (4337,4339), (4421,4423), (4481,4483), (4517,4519), (4547,4549), (4637,4639), (4649,4651), (4721,4723), (4787,4789), (4799,4801), (4931,4933), (4967,4969), (5009,5011), (5021,5023), (5099,5101), (5231,5233), (5279,5281), (5417,5419), (5441,5443), (5477,5479), (5501,5503), (5519,5521), (5639,5641), (5651,5653), (5657,5659), (5741,5743), (5849,5851), (5867,5869), (5879,5881), (6089,6091), (6131,6133), (6197,6199), (6269,6271), (6299,6301), (6359,6361), (6449,6451), (6551,6553), (6569,6571), (6659,6661), (6689,6691), (6701,6703), (6761,6763), (6779,6781), (6791,6793), (6827,6829), (6869,6871), (6947,6949), (6959,6961), (7127,7129), (7211,7213), (7307,7309), (7331,7333), (7349,7351), (7457,7459), (7487,7489), (7547,7549), (7559,7561), (7589,7591), (7757,7759), (7877,7879), (7949,7951), (8009,8011), (8087,8089), (8219,8221), (8231,8233), (8291,8293), (8387,8389), (8429,8431), (8537,8539), (8597,8599), (8627,8629), (8819,8821), (8837,8839), (8861,8863), (8969,8971), (8999,9001), (9011,9013), (9041,9043), (9239,9241), (9281,9283), (9341,9343), (9419,9421), (9431,9433), (9437,9439), (9461,9463), (9629,9631), (9677,9679), (9719,9721), (9767,9769), (9857,9859), (9929,9931)]
# Enter the largest 'number' for sieving ...
N>
 

Die Laufzeiten einschließ­lich des mit­laufen­den Pro­filers schwan­ken um einige Sekun­den, sie betra­gen 8,559 ­Sekun­den oder auch 9,775 ­Sekun­den, 10,566 ­Sekun­den, 7,005 ­Sekun­den. Wo kom­men die großen Lauf­zeit­unter­schiede bloß her?, denn eine ressour­cen­fres­sende Anwen­dung lief nicht neben­her.)

Der weitaus größte Teil der Ablauf­zeit scheint für die Verwal­tung der Ablauf­fäden aufge­wendet zu werden - wenn ich dem Pro­filer glauben schen­ken darf, wenn ich ihn über­haupt rich­tig verstehe. Nun denn, meine Umset­zung des Sieb­algo­rithmus hier ist ja auch mehr eine akade­mische Übung als auf die prak­tische Anwen­dung ausge­rich­tet:
 

  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-Inter­preter bricht jeden­falls unter der Last der Ablauf­fäden nicht so schnell zusam­men, nach eini­gen Sekun­den mehr hat er auch die Primzahlen bis 30000 bestimmt, mit nicht weni­gen, genau mit immer­hin 3245 Primz­ahl-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än­kung bei Python: Die Ablauf­fäden (threads) sind nicht mehr­kern-fähig. Es wird in der Dokumen­taion empfoh­len, dann schwer­gewich­tigere Pro­zesse zu ver­wenden. - Die Bequem­lich­keit, die eine inter­pre­tierte Pro­grammier­sprache für den Soft­ware-Ent­wick­ler bietet, hat halt auch ihren Preis.

Zwei Zitate aus der Python-Dokumentation (Python 3.4.2):

GIT - global interpreter lock
"The mechanism used by the CPython interpreter to assure that only one thread executes Python bytecode at a time. This simplifies the CPython implementation by making the object model (including critical built-in types such as dict) implicitly safe against concurrent access. Locking the entire interpreter makes it easier for the interpreter to be multi-threaded, at the expense of much of the parallelism afforded by multi-processor machines.

However, some extension modules, either standard or third-party, are designed so as to release the GIL when doing computationally-intensive tasks such as compression or hashing. Also, the GIL is always released when doing I/O.

Past efforts to create a “free-threaded” interpreter (one which locks shared data at a much finer granularity) have not been successful because performance suffered in the common single-processor case. It is believed that overcoming this performance issue would make the implementation much more complicated and therefore costlier to maintain."
...
 
"The multiprocessing package offers both local and remote concurrency, effectively side-stepping the Global Interpreter Lock by using subprocesses instead of threads. Due to this, the multiprocessing module allows the programmer to fully leverage multiple processors on a given machine. It runs on both Unix and Windows."



Quellcode für Python 3


sieve-threads-py.htm

sieve-threads.py



© 2015 Bernd Ragutt
Alle Rechte vorbehalten
 ... hier kann man hinschreiben letzte Änderung: 17. März 2018
Kruschtkiste