Hallo!
Ich habe ein Programm zum Finden von Primzahlen mit Python geschrieben. Doch lasstet es meine CPU nur zu 50 % aus. Da ich einen Dual-Core habe (T7200) nehme ich an, dass Python diesen nicht unterstützt und nur mit einem Core arbeitet.
Ich habe schon die neuste Versio (2.5.1).
Gibt es da eine Lösung, damit ich vielleicht meine ganze CPU nutzen kann und doppelt so schnell werden kann?
Danke schonmal!,
Gruß
peak
Dual-Core-Unterstützung
Vielleicht sollte man noch dazu sagen, dass kein Programm einfach so mehrere Kerne/Prozessoren benutzen kann. Der Programmierer muss da aktiv werden und den Algorithmus parallelisieren und auf mehrere Threads/Prozesse aufteilen.
Bei den üblichen Primzahl-Algorithmen, wie zum Beispiel den Sieben (Erastothenes, Atkins) sehe ich da keine Möglichkeit. Wenn so etwas einfach über mehrere Prozessoren skalieren würde, wären kryptographische Algorithmen, die auf Primzahlen setzen, etwas weniger sicher.
Bei den üblichen Primzahl-Algorithmen, wie zum Beispiel den Sieben (Erastothenes, Atkins) sehe ich da keine Möglichkeit. Wenn so etwas einfach über mehrere Prozessoren skalieren würde, wären kryptographische Algorithmen, die auf Primzahlen setzen, etwas weniger sicher.
Es gibt AFAICT parallele Algorithmen, Primzahlen zu berechnen. Es ist richtig, dass gewöhnliche Programmiersprachen Programme nicht automatisch schneller ablaufen lassen, wenn mehr Prozessoren zur Verfügung stehen. Doch es gibt Programmiersprachen, z.B. Erlang, die es so einfach machen, parallelisierbare Lösungen zu schreiben, dass es dort natürlich ist und dann profitieren diese Programme automatisch von mehrere Prozessoren. Python hat hier definitiv einen Schwachpunkt.
Eine parallele Primzahlsuche funktioniert z.B. so: Ein Prozess zählt von 2 beginnend hoch und bietet diese Zahlen als potentielle Primzahlen an. Mit jeder gefundenen Primzahl startet ein neuer Prozess, der alle Zahlen, die durch "seine" Zahl teilbar sind, nicht weiterleitet. Die Prozesse bilden eine Kette und alle Operationen in der Kette können parallel ausgeführt werden. Aufgrund des Kommunikationsoverheads wird dieser Algorithmus bei kleinen Bereichen jedem sequentiellen Algorithmus unterlegen sein, aber irgendwo mag die Grenze liegen und dann ist er schneller als nur ein Prozessor es könnte.
Stefan
Eine parallele Primzahlsuche funktioniert z.B. so: Ein Prozess zählt von 2 beginnend hoch und bietet diese Zahlen als potentielle Primzahlen an. Mit jeder gefundenen Primzahl startet ein neuer Prozess, der alle Zahlen, die durch "seine" Zahl teilbar sind, nicht weiterleitet. Die Prozesse bilden eine Kette und alle Operationen in der Kette können parallel ausgeführt werden. Aufgrund des Kommunikationsoverheads wird dieser Algorithmus bei kleinen Bereichen jedem sequentiellen Algorithmus unterlegen sein, aber irgendwo mag die Grenze liegen und dann ist er schneller als nur ein Prozessor es könnte.
Stefan
Danke für die schnellen Antworten.
Jetzt weiß ich ja, wonach ich suchen muss; werde mir das mal durchlesen.
In der Zwischenzeit habe ich jetzt das Programm zweimal laufen. Dann wird die CPU auch zu 100 % ausgelastet.
Mein Programm braucht übrigens 0,047 Sekunden, um alle Primzahlen bis 1000 zu suchen. Ist das gut?^^
Gruß
peak
Jetzt weiß ich ja, wonach ich suchen muss; werde mir das mal durchlesen.
In der Zwischenzeit habe ich jetzt das Programm zweimal laufen. Dann wird die CPU auch zu 100 % ausgelastet.
Mein Programm braucht übrigens 0,047 Sekunden, um alle Primzahlen bis 1000 zu suchen. Ist das gut?^^
Gruß
peak
- Hobbes Hobson
- User
- Beiträge: 42
- Registriert: Sonntag 9. Dezember 2007, 15:24
- Wohnort: Bremen
Also mit meinem Quadcore habe ich je nach verfahren ca. 0.0 oder ca. 0.015 Sekunden gebraucht.
Poste doch mal dein Programm hier rein, damit wir das analysieren und ausprobieren können.
Poste doch mal dein Programm hier rein, damit wir das analysieren und ausprobieren können.
Hier mal mein Programm, das nach dem Sieb-des-Eratosthenes-Prinzip funktioniert:
Dazu habe ich folgedne Fragen:
Wie ist die Syntax für die dritte Wurzel? x**(1/3) funktioniert nicht.
Kann man einen try/except-Fall auch ohne except machen? Bei mir geht das nämlich nicht.
Edit (BlackJack): Code Tags gesetzt.
Code: Alles auswählen
grenze=input('Bis wo soll gerechnet werden?')
ngrenze=grenze/2
import time
t1=time.time()
num=[]
x=0
zahl=1
for j in range(0,grenze):
x=x+1
num.append(x)
while zahl < ngrenze:
zahl=zahl+1
alte=zahl
while alte+zahl <= grenze:
neue=alte+zahl
alte=neue
try:
num.remove(neue)
except:
1+1
t2=time.time()
print 'Die Primzahlen lauten: ', num
print 'Die benötigte Zeit beträgt ', t2-t1, ' Sekunden.'
warte = raw_input('beenden mit <enter>')
Wie ist die Syntax für die dritte Wurzel? x**(1/3) funktioniert nicht.
Kann man einen try/except-Fall auch ohne except machen? Bei mir geht das nämlich nicht.
Edit (BlackJack): Code Tags gesetzt.
Du meinst wahrscheinlich die Codetags.Peak_me hat geschrieben:Wie bekommt man diesen schönen Zitier-Modus?
Einfach oben in der Leiste den Button 'Python', dann deinen Code einfügen und dann denselben wieder.
[code]q = 'q = %s; print q %% repr(q)'; print q % repr(q) [/code]
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
Importe sollte man ganz oben im Code stehen haben, ``input()`` hingegen komplett vermeiden. Warum x**(1/3) nicht funktioniert (gibt immer 1) ist auch einfach zu klären: 1/3 = 0, denn es geht hier um Ganzzahldivision. Du müsstest also 1.0/3.0 oder ähnlich rechnen bzw. ``from __future__ import division`` an den Anfang des Moduls schreiben.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
@Peak_me: Da ist einiges etwas umständlich.
Die erste ``for``-Schleife: Die `range()`-Funktion liefert bereits eine Liste mit Zahlen:
Die beiden ``while``-Schleifen lassen sich auch mit ``for``-Schleifen und `xrange()` ausdrücken und damit dann auch ein paar Zeilen einsparen.
Die Leeranweisung heisst ``pass``.
Allerdings ist diese Art mit `remove()` fürchterlich langsam weil jedesmal die gesamte Liste nach `neue` durchsucht wird. Üblicherweise erzeugt man vorher eine Liste mit Flags (Index = Zahl) und "streicht" die Nicht-Primzahlen, in dem man den Index auf `False` setzt. Dann muss man weder linear suchen noch beim Entfernen alle nachfolgenden Elemente eins nach unten kopieren.
Die erste ``for``-Schleife: Die `range()`-Funktion liefert bereits eine Liste mit Zahlen:
Code: Alles auswählen
In [355]: range(10, 21)
Out[355]: [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
Die Leeranweisung heisst ``pass``.
Allerdings ist diese Art mit `remove()` fürchterlich langsam weil jedesmal die gesamte Liste nach `neue` durchsucht wird. Üblicherweise erzeugt man vorher eine Liste mit Flags (Index = Zahl) und "streicht" die Nicht-Primzahlen, in dem man den Index auf `False` setzt. Dann muss man weder linear suchen noch beim Entfernen alle nachfolgenden Elemente eins nach unten kopieren.
-
- User
- Beiträge: 102
- Registriert: Dienstag 25. Dezember 2007, 22:53
- Wohnort: Freiburg im Breisgau
Code: Alles auswählen
for j in range(0,grenze):
x=x+1
num.append(x)
Code: Alles auswählen
while zahl < ngrenze:
zahl=zahl+1
alte=zahl
while alte+zahl <= grenze:
neue=alte+zahl
alte=neue
try:
num.remove(neue)
except:
1+1
Dir gehts um Geschwindigkeit und du benutzt .remove? Ich weiss nicht genau, wie so eine Liste intern aufgebaut ist, aber das ist sicher in O(n). Anstatt dem 1+1 könntest du auch ein 'pass' schreiben.
Eine Alternative, wäre eine Liste aus 2-Tuppeln (n,bool). In den boolean könntest du dann eintragen, ob die Zahl schon als nicht-prim erkannt wurde.
Du brauchst auch deine Schleife nicht bis zur Grenze laufen lassen. Bis sqrt(grenze) reicht völlig.
(Beweis: Sei z eine nicht-Primzahl<grenze, für die bis zum Durchlauf bis sqrt(grenze) kein Teiler bis auf 1 gefunden wurde. Das bedeutet, dass sie zwei Teiler hat, die jeweils größer als sqrt(g) sind, das Produkt liegt somit über der grenze, im Widerspruch zur Annahme dass s<grenze).
Damit kannst dir grob 960 von deinen Tausend überprüfungen sparen
// P.S.: Da BlackJack leider schneller getippt hat, hier noch ein Alleinstellungsmerkmal meines Beitrags: schau dir mal das modul profile an. Da kannst du einen Funktionsaufruf übergeben und die wird ziemlich genau gesagt, für welchen deiner benutzen Befehle wie viel Zeit benötigt wurde.
Erwarte das Beste und sei auf das Schlimmste vorbereitet.
Also auf die Schnelle das Ganze mit nem Dictionary.
Code: Alles auswählen
from math import sqrt
def find_primes(limit):
test_nums = dict([[i,True] for i in xrange(2,limit)])
for n in xrange(2,limit):
if test_nums[n]:
yield n
if n <= sqrt(limit):
for key in test_nums.iterkeys():
if not key % n:
test_nums[key]=False
def main():
limit=10000
print [prime for prime in find_primes(limit)]
if __name__ == '__main__':
main()
-
- User
- Beiträge: 102
- Registriert: Dienstag 25. Dezember 2007, 22:53
- Wohnort: Freiburg im Breisgau
Das dict dürfte auch nicht das schnellste sein.
Es gibt doch auch in Python arrays, die in O(1) auf ein Element zugreifen können. Bei so einem dict erwarte ich intern einen balancierten Baum, so dass lesen und setzen in O(log n) ist.
Mein Vorschlag wäre deswegen ein array of Booleans zu nehmen. Wenn man dann über eine Schleife (for i in range(2,grenze)) auf array zugreift, braucht man überhaupt integer-Eintragungen in der Liste.
Und etwas schnelleres, als ein Boolean in einem Array zu finden und zu testen, dürfte es nicht geben.
Es gibt doch auch in Python arrays, die in O(1) auf ein Element zugreifen können. Bei so einem dict erwarte ich intern einen balancierten Baum, so dass lesen und setzen in O(log n) ist.
Mein Vorschlag wäre deswegen ein array of Booleans zu nehmen. Wenn man dann über eine Schleife (for i in range(2,grenze)) auf array zugreift, braucht man überhaupt integer-Eintragungen in der Liste.
Und etwas schnelleres, als ein Boolean in einem Array zu finden und zu testen, dürfte es nicht geben.
Erwarte das Beste und sei auf das Schlimmste vorbereitet.
- veers
- User
- Beiträge: 1219
- Registriert: Mittwoch 28. Februar 2007, 20:01
- Wohnort: Zürich (CH)
- Kontaktdaten:
Code: Alles auswählen
from math import sqrt
def find_primes(limit):
sieve = [True]*limit
sqrtlimit = sqrt(limit)
for prime in (n for n in xrange(2, limit) if sieve[n]):
yield prime
if prime <= sqrtlimit:
for n in xrange(prime, limit):
if not n % prime:
sieve[n] = False
In [47]: timeit list(find_primes(1000))
100 loops, best of 3: 2.34 ms per loop
Code: Alles auswählen
def find_primes(limit):
sieve = [True]*limit
primes = []
sqrtlimit = int(sqrt(limit))
for n in xrange(2, limit):
if sieve[n]:
primes.append(n)
if n <= sqrtlimit:
x = limit / n
for i in xrange(2, x):
sieve[n*i] = False
return primes
In [55]: timeit list(find_primes(1000))
1000 loops, best of 3: 589 µs per loop
100 loops, best of 3: 2.88 ms per loop
Viel macht es nicht aus
Ich frage mich jedoch ernsthaft weshalb man für derart Performance kritische Programme Python verwenden sollte
Zuletzt geändert von veers am Dienstag 29. Januar 2008, 15:27, insgesamt 5-mal geändert.
[url=http://29a.ch/]My Website - 29a.ch[/url]
"If privacy is outlawed, only outlaws will have privacy." - Phil Zimmermann
"If privacy is outlawed, only outlaws will have privacy." - Phil Zimmermann
- Hobbes Hobson
- User
- Beiträge: 42
- Registriert: Sonntag 9. Dezember 2007, 15:24
- Wohnort: Bremen
- veers
- User
- Beiträge: 1219
- Registriert: Mittwoch 28. Februar 2007, 20:01
- Wohnort: Zürich (CH)
- Kontaktdaten:
Hast du meinen Code gelesen?Hobbes Hobson hat geschrieben:Wie wäre es mit dem Sieb des Eratosthenes?
http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes
[url=http://29a.ch/]My Website - 29a.ch[/url]
"If privacy is outlawed, only outlaws will have privacy." - Phil Zimmermann
"If privacy is outlawed, only outlaws will have privacy." - Phil Zimmermann
-
- User
- Beiträge: 102
- Registriert: Dienstag 25. Dezember 2007, 22:53
- Wohnort: Freiburg im Breisgau
@Hobbes:
Du hast den Thread nicht gelesen, oder?
@Veers:
> sieve = [True]*limit
Das ist doch eine verkette Liste, oder? (wahrscheinlich doppelt, damit man sie schnell umdrehen kann).
Wenn man das noch in eine Array (wie in Pascal, C++, Java) umwandelt, dürfte das nochmal ein bischen schneller werden.
> Ich frage mich jedoch ernsthaft weshalb man für derart Performance kritische Programme Python verwenden sollte
Ist doch mal ganz interessant. Einen wirklichen Nutzen hat das Programm sowieso nicht, daher steht der Lerneffekt im Vordergrund.
Du hast den Thread nicht gelesen, oder?
@Veers:
> sieve = [True]*limit
Das ist doch eine verkette Liste, oder? (wahrscheinlich doppelt, damit man sie schnell umdrehen kann).
Wenn man das noch in eine Array (wie in Pascal, C++, Java) umwandelt, dürfte das nochmal ein bischen schneller werden.
> Ich frage mich jedoch ernsthaft weshalb man für derart Performance kritische Programme Python verwenden sollte
Ist doch mal ganz interessant. Einen wirklichen Nutzen hat das Programm sowieso nicht, daher steht der Lerneffekt im Vordergrund.
Erwarte das Beste und sei auf das Schlimmste vorbereitet.
- veers
- User
- Beiträge: 1219
- Registriert: Mittwoch 28. Februar 2007, 20:01
- Wohnort: Zürich (CH)
- Kontaktdaten:
Dachte ich auch. Ist aber ähnlich wie ein C++ Vektor.Nikolas hat geschrieben: @Veers:
> sieve = [True]*limit
Das ist doch eine verkette Liste, oder? (wahrscheinlich doppelt, damit man sie schnell umdrehen kann).
Wenn man das noch in eine Array (wie in Pascal, C++, Java) umwandelt, dürfte das nochmal ein bischen schneller werden.
[url=http://29a.ch/]My Website - 29a.ch[/url]
"If privacy is outlawed, only outlaws will have privacy." - Phil Zimmermann
"If privacy is outlawed, only outlaws will have privacy." - Phil Zimmermann
@Nikolas: Listen sind als dynamische Arrays implementiert und Dictionaries als Hash-Tabellen. Benötigt also beides beim Zugriff auf Elemente O(1) Zeit.