Python beschleunigen: Pyrex, weave, C++, Cython -- und nun?

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.
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Sonntag 8. Mai 2011, 18:52

lunar hat geschrieben:@Leonidas: Wieso sollte "gauss(c, d)" konstant sein?!
Sorry, heute ist wohl nicht mein Tag. Bin schon seit Stunden dabei, mit EFI zu kämpfen :(
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Tyrax
User
Beiträge: 73
Registriert: Mittwoch 4. Februar 2009, 18:31

Sonntag 8. Mai 2011, 21:29

@BlackJack: Ich habe versucht, ein Minimalbeispiel hinzuschreiben, dass die auftretenden Methoden enthält. Das sollte keine Geheimniskrämerei sein sondern lediglich das Problem auf das Wesentliche reduzieren.

Wenn man - wie Du richtig schreibst - herausfinden will, wann sich zwei Random Walker treffen, muss man natürlich auch noch ein Intervall definieren, wo die beiden herumirren und im Fall normalverteilter Schrittlängen auch noch eine "Kontaktdistanz" damit der Prozess auch mal zu einem Ende kommt. Dazu kommen noch ein paar andere Paramter, die imho für die Beschleunigung nicht entscheidend sind.

Wenn ich weiß, wie ich meine dummeFunktion schneller bekomme, kann ich das auf mein aktuelles und ggf. auf andere Probleme anwenden.

@HerrHagen: Da ich nicht vorher weiß, wann der Prozess endet, habe ich wenig davon 10^4 Zufallszahlen auf einmal zu ziehen - es kann halt immer sein, dass ich nur die ersten zwei brauche. Falls numpy auch für einzelne Zufallszahlen deutlich schneller ist, würde mich Dein Vorschlag weiterbringen.

Meine Beispielfunktion ist tatsächlich ziemlich sinnlos (daher der Name), es sollte halt ein Minimalbsp sein.


Beste Grüße, Tyrax
BlackJack

Montag 9. Mai 2011, 07:56

@Tyrax: Man kann so halt nicht so gut Abschätzen wie umfangreich so etwas zum Beispiel in C wird. Manche Python-Zeilen lassen sich in wenigen C-Zeilen ausdrücken, in anderen Fällen bräuchte man für eine Python-Zeile deutlich mehr in C oder vielleicht sogar eine Bibliothek, damit sich eine Umsetzung lohnt.

Als Vorbereitung würde ich erst einmal ein paar "seeds" für den Zufallsgenerator suchen bei dem die beiden Walker etwas länger unterwegs sind, oder vielleicht noch besser den Test ob sie sich getroffen haben durch einen Zähler ersetzen. Dann hast Du zwar nicht mehr ganz das was Du letztendlich beschleunigen willst, aber die ganzen Rechenschritte sind drin und man kann verschiedene Läufe besser miteinander vergleichen.

Ich würde an Deiner Stelle erst einmal `psyco` ausprobieren. Wenn das möglich ist und hinreichend beschleunigt, dann ist das wohl am wenigsten Arbeit.

Als zweites könnte man Cython versuchen und da so viel wie möglich in Richtung "C" verschieben. Inklusive der `random.Random.gauss()`-Implementierung.

Falls das nicht schnell genug wird, würde ich es komplett in C als Bibliothek/DLL programmieren und über `ctypes` darauf zugreifen. Da müsste man sich dann aber eine äquivalente Quelle für Zufallszahlen suchen. Die Glib hat zum Beispiel einen "Mersenne Twister", der mit `g_random_double()` auch sehr einfach zu benutzen ist.
Tyrax
User
Beiträge: 73
Registriert: Mittwoch 4. Februar 2009, 18:31

Montag 9. Mai 2011, 19:12

@BlackJack: Danke, Dein letzter Beitrag ist in etwa die Einsicht, die ich von dem thread erhofft hatte. Wahrscheinlich hätte ich die Diskussion durch einen exaktere Problembeschreibung beschleunigen können ...

Wegen Psyco: Ich habe mir mal die mutmaßliche Homepage http://psyco.sourceforge.net angesehen, auf der auf das Nachfolgeprojekt PyPy hingewiesen wird. Ich habe mir dazu einige Seiten angesehen und hatte den Eindruck, dass PyPy keine Nachteile gegenüber Psyco hat. Liege ich da richtig?
BlackJack

Montag 9. Mai 2011, 19:54

@Tyrax: `psyco` ist ein Modul für CPython und PyPy ist eine komplette Python-Implementierung. Wenn Du Dein Programm mit PyPy laufen lassen kannst, also keine Abhängigkeiten hast, die mit PyPy nicht funktionieren, dann ginge das natürlich auch.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Montag 9. Mai 2011, 20:25

Tyrax hat geschrieben:Wegen Psyco: Ich habe mir mal die mutmaßliche Homepage http://psyco.sourceforge.net angesehen, auf der auf das Nachfolgeprojekt PyPy hingewiesen wird. Ich habe mir dazu einige Seiten angesehen und hatte den Eindruck, dass PyPy keine Nachteile gegenüber Psyco hat. Liege ich da richtig?
Ein "Nachteil" könnte die schlechtere Performance sein - das hängt jedoch stark vom Einzelfall ab. Im konkreten Fall - Verwendung von random.gauss() - tun sich die beiden so gut wie nichts. Die Laufzeit halbiert sich in etwa im Vergleich zum normalen CPython. Die schnellste Laufzeit liefert auf meinem Rechner pypy-1.3 (verglichen mit pypy-1.4, pypy-1.5 und psyco).
Benutzeravatar
b.esser-wisser
User
Beiträge: 272
Registriert: Freitag 20. Februar 2009, 14:21
Wohnort: Bundeshauptstadt B.

Dienstag 10. Mai 2011, 08:36

Evtl kannst du das noch beschleunigen, in dem du den float-Vergleich 'richtig' machst ('abs(x-y) < EPSILON', mit einem passenden EPSILON).
Folgendes braucht hier ~3min, die originale Funktion ist nach ~20min noch nicht fertig.

Code: Alles auswählen

def dummy_funktion(a, b, c, d):
    gauss = random.gauss
    eps = 1.0e-8
    while True:
        x = gauss(a, b)
        y = gauss(c, d)
        if abs(x-y) < eps:
            break
    return x
Wir haben schon 10% vom 21. Jahrhundert hinter uns!
Tyrax
User
Beiträge: 73
Registriert: Mittwoch 4. Februar 2009, 18:31

Dienstag 10. Mai 2011, 12:49

Danke für den Hinweis, aber dass die ursprünglich von mir gepostete Funktion kein sinnvolles Problem beschreibt, wurde schon mehrfach angemerkt. Dein epsilon ist gerade die 'Kontaktdistanz' die ich in meinem vorletzten Beitrag erwähnt hatte. Der von Dir vorgeschlagene dummy_Funktion ist imho schneller, weil sie einfach etwas anderes simuliert.

Naja, ich werde mir in Zukunft alle Mühe geben, etwas weniger sinnlose Minimalbeispiele zu basteln.
JonasR
User
Beiträge: 251
Registriert: Mittwoch 12. Mai 2010, 13:59

Dienstag 10. Mai 2011, 15:38

b.esser-wisser hat geschrieben:Folgendes braucht hier ~3min, die originale Funktion ist nach ~20min noch nicht fertig.
Solltest die Aussage nochmal überdenken :P Es ist doch gar nicht gesagt dass beide Aufrufe die gleiche Anzahl an Durchläufen brauchten.
Wenn ich jetzt etwas an der Funktion umschreibe und sie zufällig nach einem Durchlauf fertig ist ist es nicht unbedingt die performanteste.
Benutzeravatar
b.esser-wisser
User
Beiträge: 272
Registriert: Freitag 20. Februar 2009, 14:21
Wohnort: Bundeshauptstadt B.

Dienstag 10. Mai 2011, 16:28

@JonasR: ich hab random schon vor jedem Test gleich ge-seed()-et
Tyrax
User
Beiträge: 73
Registriert: Mittwoch 4. Februar 2009, 18:31

Dienstag 10. Mai 2011, 17:19

@b.esser-wisser: Wie ich schon geschrieben habe: Der Grund dafür, dass Deine Funktion schneller ist, liegt einfach darin, dass Du einen anderen Prozess simulierst. Du kannst ja mal die Schleifendurchläufe in beiden mitzählen und das prüfen.

An der Stelle bringt auch ein identischer Seed nix.
Antworten