Das deutsche Python-Forum

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

Hallo peak_me, willkommen im Forum,

Multithreaded C Module.

(Für die lange Antwort such im Forum nach GIL)

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.

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

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

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.

Hier mal mein Programm, das nach dem Sieb-des-Eratosthenes-Prinzip funktioniert:

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>')

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.

ARG
Wie bekommt man diesen schönen Zitier-Modus?

Peak_me hat geschrieben:Wie bekommt man diesen schönen Zitier-Modus?

Du meinst wahrscheinlich die Codetags.

Einfach oben in der Leiste den Button 'Python', dann deinen Code einfügen und dann denselben wieder.

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.

@Peak_me: Da ist einiges etwas umständlich.

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 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.

Code: Alles auswählen

for j in range(0,grenze):
        x=x+1
        num.append(x)

Weisst du, was du da machst? range gibt doch schon die passende Liste zurück. Du baust dir also eine Liste auf, nur um dann eine identische Kopie anzufertigen..., die Null brauchst du auch nicht anzugeben.

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.

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()

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.

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

Und noch xoxox code:
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

Wie wäre es mit dem Sieb des Eratosthenes?

http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes

Hobbes Hobson hat geschrieben:Wie wäre es mit dem Sieb des Eratosthenes?

http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes

Hast du meinen Code gelesen?

@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.

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.

Dachte ich auch. Ist aber ähnlich wie ein C++ Vektor.

@Nikolas: Listen sind als dynamische Arrays implementiert und Dictionaries als Hash-Tabellen. Benötigt also beides beim Zugriff auf Elemente O(1) Zeit.

Das deutsche Python-Forum

Dual-Core-Unterstützung

Dual-Core-Unterstützung