Dual-Core-Unterstützung

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Peak_me
User
Beiträge: 92
Registriert: Sonntag 27. Januar 2008, 03:09

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
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Hallo peak_me, willkommen im Forum,

Multithreaded C Module.

(Für die lange Antwort such im Forum nach GIL)
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
BlackJack

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.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

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
Peak_me
User
Beiträge: 92
Registriert: Sonntag 27. Januar 2008, 03:09

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
Benutzeravatar
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.
Peak_me
User
Beiträge: 92
Registriert: Sonntag 27. Januar 2008, 03:09

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.
Peak_me
User
Beiträge: 92
Registriert: Sonntag 27. Januar 2008, 03:09

ARG
Wie bekommt man diesen schönen Zitier-Modus?
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

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.
[code]q = 'q = %s; print q %% repr(q)'; print q % repr(q) [/code]
Leonidas
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
BlackJack

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

:shock: 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 :lol:

// 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.
xoxox
User
Beiträge: 12
Registriert: Dienstag 11. September 2007, 13:51

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()
Nikolas
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.
Erwarte das Beste und sei auf das Schlimmste vorbereitet.
Benutzeravatar
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
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 ;)
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
Benutzeravatar
Hobbes Hobson
User
Beiträge: 42
Registriert: Sonntag 9. Dezember 2007, 15:24
Wohnort: Bremen

Wie wäre es mit dem Sieb des Eratosthenes?

http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes
Benutzeravatar
veers
User
Beiträge: 1219
Registriert: Mittwoch 28. Februar 2007, 20:01
Wohnort: Zürich (CH)
Kontaktdaten:

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? ;)
[url=http://29a.ch/]My Website - 29a.ch[/url]
"If privacy is outlawed, only outlaws will have privacy." - Phil Zimmermann
Nikolas
User
Beiträge: 102
Registriert: Dienstag 25. Dezember 2007, 22:53
Wohnort: Freiburg im Breisgau

@Hobbes:
Du hast den Thread nicht gelesen, oder? :roll:

@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.
Benutzeravatar
veers
User
Beiträge: 1219
Registriert: Mittwoch 28. Februar 2007, 20:01
Wohnort: Zürich (CH)
Kontaktdaten:

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.
[url=http://29a.ch/]My Website - 29a.ch[/url]
"If privacy is outlawed, only outlaws will have privacy." - Phil Zimmermann
BlackJack

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