Seite 2 von 2

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Sonntag 8. Mai 2011, 18:52
von Leonidas
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 :(

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Sonntag 8. Mai 2011, 21:29
von Tyrax
@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

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Montag 9. Mai 2011, 07:56
von BlackJack
@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.

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Montag 9. Mai 2011, 19:12
von Tyrax
@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?

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Montag 9. Mai 2011, 19:54
von BlackJack
@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.

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Montag 9. Mai 2011, 20:25
von numerix
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).

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Dienstag 10. Mai 2011, 08:36
von b.esser-wisser
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

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Dienstag 10. Mai 2011, 12:49
von Tyrax
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.

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Dienstag 10. Mai 2011, 15:38
von JonasR
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.

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Dienstag 10. Mai 2011, 16:28
von b.esser-wisser
@JonasR: ich hab random schon vor jedem Test gleich ge-seed()-et

Re: Python beschleunigen: Pyrex, weave, C++, Cython -- und n

Verfasst: Dienstag 10. Mai 2011, 17:19
von Tyrax
@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.