Primzahlenberechnung, Effiziente Speicherung
Hallo zusammen! Da dies mein erster Kontakt mit einer Mailingliste ist, möchte ich euch bitten mir nachzusehen, dass ich mit der Arbeitsweise noch nicht ganz vertraut bin. Nun zu meiner Frage, bzw. zu meinem Problem: Ich habe ein Programm geschrieben, dass mir die ersten n Primzahlen ausrechnet und dies durch verschiedene Maßnahmen optimiert, welche die Rechenzeit stark verkürzen. Beispielsweise genügt es, wenn man die zu überprüfende Zahl auf Teilbarkeit durch alle ungeraden Zahlen von 3 bis zur Quadratwurzel der Zahl überprüft, um zu ermitteln, ob es sich um eine Primzahl handelt. Dieses Programm benötigt zur Errechnung der ersten 10.000 Primzahlen auf meinem Rechner geschätzt ca. 2-3 Sekunden. Nun lässt sich das Programm jedoch noch weiter optimieren, denn theoretisch muss man nicht auf Teilbarkeit durch alle ungeraden Zahlen prüfen, sondern nur durch Teilbarkeit durch die vorherigen Primzahlen. Hierzu ist es jedoch notwendig die errechneten Primzahlen in einer Liste zu speichern. Die Vorteile der Listen dynamischer Länge, die es in Python gibt liegen auf der Hand, jedoch sind sie in Ihrer Anwendung leider sehr langsam, da das Programm, wenn auf das n'te Element der Liste zugegriffen werden soll, zuerst alle Elemente von 0 bis n-1 durchlaufen muss, um zum Element n zu gelangen. Bei einer Liste der Länge 10.000 bedeutet dies einen großen Zeitaufwand. Das Programm, das vorher 2-3 Sekunden benötigte brauch nun, in der mathematisch optimierten Form, fast 20 Sekunden. Gibt es eine Möglichkeit Listen in Python zu erstellen, auf welche schneller zugegriffen werden kann? In vielen anderen Programmiersprachen (java, c++, etc.) kann man ja zusätzlich zu den dynamischen Listen, Vektoren auch Listen einer vordefinierten Länge anlegen, die wesentlich schneller verarbeitet werden können, weil der Speicherort von jedem Element nach der Erstellung feststeht. Gibt es in Python auch eine Möglichkeit dies zu realisieren? Vielen Dank für eure Hilfe! Hier habt ihr nochmal den derzeitigen Programmcode des Primzahlenrechners (könnte ich ihn auch als Anlage beilegen? [code] import math anzahl = int(raw_input("Geben Sie die Anzahl der zu errechnenden Primzahlen an: ")) zaehler = 2 pruefen = 5 gefunden = [2,3] darstell = "" while zaehler < anzahl: istprim = True for i in gefunden: if (pruefen % i == 0) and (i<(math.sqrt(pruefen)+1)): istprim = False break if istprim == True: gefunden.append(pruefen) zaehler += 1 pruefen +=2 for i in range(1,len(gefunden)): if (i+1)%10 > 0: darstell += str(gefunden[i]) + " " else: darstell += str(gefunden[i]) + " " print darstell darstell = "" [/code]
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 26.01.2009 12:26 Uhr, Robert Heumüller wrote:
Dein Problem ist eher der Algorithmus. Warum verwendet Du nicht einen Standardalgorithmus wie Sieb des Erathostenes? http://www.little-idiot.de/python/x388.html Andreas -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (Darwin) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkl9prkACgkQCJIWIbr9KYwlxACfRN9JXEMbjvbNPcf44PvYzy1V 6S8AmwYrPOqEgAZdK6gbMEpgA6WLZZVO =MuNW -----END PGP SIGNATURE-----
Andreas Jung schrieb:
Na ja, ganz so einfach ist es auch wieder nicht. Der in diesem Link gezeigte Algorithmus dürfte auch nicht (signifikant) schneller sein als Roberts. Aber ein kleine Änderung def PrimesLE(limit): Primes = [2] counter = 3 while counter <= limit : for KnownPrime in Primes: if counter % KnownPrime == 0: break elif KnownPrime*KnownPrime > counter: Primes.append(counter) break counter = counter + 2 return Primes macht ihn gleich um einen Faktor 30 schneller (für limit = 100000). Beste Grüße Gregor
Robert,
also ... das n-te element einer Liste bekommst Du mit liste[n] und zwar in O(1), also konstanter Zeit. Gruß Harald -- GHUM Harald Massa persuadere et programmare Harald Armin Massa Spielberger Straße 49 70435 Stuttgart 0173/9409607 no fx, no carrier pigeon - EuroPython 2009 will take place in Birmingham - Stay tuned!
<snip/> Woher kommst du auf diese Idee? Python's listen sind mitnichten als verkettete Listen implemnetiert, sondern stattdessen als dynamisch wachsende Arrays mit O(1) fuer lesen und schreiben. Wie anhaengen genau implementiert ist, kann ich nicht sagen - ich weiss, das irgendwo (koennen aber auch dicts sein) der speicherbedarf bis zu einer bestimmten Grenze verdoppelt wird, und danach nur noch proportional waechst. Aber das sollte alles fuer dein Problem ueberhaupt keine Rolle spielen - da geht dir eher die Lust & Zeit aus, als das die Performance der Listen degradiert. Diez
Robert Heumüller schrieb:
[...]
Hier habt ihr nochmal den derzeitigen Programmcode des Primzahlenrechners (könnte ich ihn auch als Anlage beilegen?
Hallo Rob, zum Thema Anlage: Nicht jeder mag Anhänge von unbekannter Herkunft öffnen. Hierfür gibt es pastebin [1][2]. Dort kann man sogar mit Syntax-Hochlicht veröffentlichen. Das gibt es auch für Bilder. Solltest Du also auch ein Screenshot in die Diskussion einbringen, dann nicht in den Anhang! Mathias [1] http://pastebin.com/d20ff73a1 [2] http://de.wikipedia.org/wiki/Pastebin
Robert Heumüller schrieb:
zufällig haben sich ein paar Leute vor ein, zwei Wochen mit diesem Problem beschäftigt, und dabei sind so ca. 6, 7 Primzahlprogramme mit unterschiedlichen Algorithmen und verwendeten Datentypen vorgestellt worden. Eine Zusammenfassung findest du hier: http://mail.python.org/pipermail/edu-sig/2009-January/009028.html Es lohnt aber vielleicht den ganzen Diskussionsfaden (apropos "Hochlicht") durchzusehen. Beste Grüße, Gregor
Beispielsweise genügt es, ....
participants (6)
-
Andreas Jung
-
Diez B. Roggisch
-
Gregor Lingl
-
Harald Armin Massa
-
Mathias Uebel
-
Robert Heumüller