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.
Tyrax
User
Beiträge: 73
Registriert: Mittwoch 4. Februar 2009, 18:31

Freitag 6. Mai 2011, 21:02

Hallo Gemeinde,

ich möchte einen Teil meines Codes beschleunigen und weiß nicht, was ich dafür verwenden soll. Zwei threads im Forum und einige weitere Quellen, helfen mir nicht wirklich. Hier mal die Eckdaten:

- In Python läuft mein Code, wenn auch mutmaßlich sehr langsam.
- Ich kann bisher weder C(++) noch FORTRAN.
- Der langsame Teil meines Python-Codes braucht nicht viel mehr als das folgende (sinnlose) Programm:

Code: Alles auswählen

def dummeFunktion(a, b, c, d):
  import random
  check = 0
  while check==0:
    x = random.gauss(a, b)
    y = random.gauss(c, d)
    if x==y:
      check = 1
  return x
Mein Ziel ist wie gesagt, den Code zu beschleunigen, mein Wunsch wäre, dafür nicht erstmal ernsthaft C++ lernen zu müssen.

Wie sollte ich am besten vorgehen und was sollte ich verwenden (zum Beispiel aus der Liste im Titel)?

Danke und beste Grüße, Tyrax
BlackJack

Freitag 6. Mai 2011, 21:59

@Tyrax: Welcher konkrete Code beschleunigt werden soll kann wichtig bei der Auswahl des Werkzeugs sein. Oder vielleicht auch bei der Frage ob es sich überhaupt sinnvoll beschleunigen lässt. Bei dem gezeigten Beispiel würde ich das zum Beispiel verneinen. Das erscheint mir in jeder Sprache unsinnig. Ob man da nun in Python, Fortran, C, oder sonstwas drauf wartet…

Aus der Liste würde ich Pyrex rauswerfen, denn Cython kann im Grunde das gleiche und dann noch mehr. Mit `weave` habe ich keine Erfahrung und um C++ würde ich persönlich einen Bogen machen. C käme eventuell in Frage. `psyco` fehlt in der Liste.

Es gibt keine magische Lösung, man muss schon schauen und ausprobieren was bei dem konkreten Problem etwas bringt.
Benutzeravatar
pillmuncher
User
Beiträge: 1185
Registriert: Samstag 21. März 2009, 22:59
Wohnort: München

Freitag 6. Mai 2011, 22:04

Wenn man wüsste wie dein langsamer Code aussieht, könnte man vielleicht ein paar Tips geben, wie man ihn verschnellern könnte. Ihn einfach mal auf gut Glück in C++ nachzubauen ist wenig sinnvoll, wenn du nicht schon von vornherein weißt, wo der Flaschenhals sitzt. Also bitte herzeigen.
In specifications, Murphy's Law supersedes Ohm's.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Samstag 7. Mai 2011, 09:59

die gezeigte Funktion hängt eigentlich nur von der Bibliotheksfunktion random.gauss und deren Performance ab. Sie ist implementiert als:

Code: Alles auswählen

def gauss(self, mu, sigma):
        random = self.random
        z = self.gauss_next
        self.gauss_next = None
        if z is None:
            x2pi = random() * TWOPI
            g2rad = _sqrt(-2.0 * _log(1.0 - random()))
            z = _cos(x2pi) * g2rad
            self.gauss_next = _sin(x2pi) * g2rad

        return mu + z*sigma
random() selbst ist eine C-Funktion. Das gilt garantiert auch für _sqrt, _log, _cos und _sin. Wenn überhaupt, lohnt es daher, eine schnellere Funktion für diese Gauss-Verteilung zu finden. Sei es ein besserer Algorithmus (falls es den gibt) oder eben davon direkt eine Implementation in C.

Das gezeigte Programm selbst lohnt nicht zu optimieren, weil es selbst vernachlässigbar ist, was die Zeit angeht - ne while-Schleife und ein Test und eine Variablenzuweisung. Man könnte es so umschreiben:

Code: Alles auswählen

import random # rausziehen!
def dummeFunktion(a, b, c, d):
  while True:
    x = random.gauss(a, b)
    if x == random.gauss(c, d):
      return x
Stefan
BlackJack

Samstag 7. Mai 2011, 10:04

Man könnte noch den Attributzugriff eliminieren:

Code: Alles auswählen

from random import gauss

def dumme_funktion(a, b, c, d):
    while True:
        x = gauss(a, b)
        if x == gauss(c, d):
            return x
Und vielleicht wäre es eine gute Idee vor Eintritt in die Schleife zu prüfen ob die Bedingung jemals erfüllbar ist. :-)
Benutzeravatar
noisefloor
User
Beiträge: 2977
Registriert: Mittwoch 17. Oktober 2007, 21:40
Wohnort: Görgeshausen
Kontaktdaten:

Samstag 7. Mai 2011, 14:30

Hallo,

@Tyrax: Willst du denn nur diese ein Funktion "schnell" implementieren und der Rest bleibt Python?

Und ob das ganze schnell oder langsam ist hängt ja auch davon ab, wie oft die while-Schleife durchlaufen wird. Im Idealfall ist es ja nur 1x - dafür muss man nicht optimieren. ;-)

Gruß, noisefloor
Tyrax
User
Beiträge: 73
Registriert: Mittwoch 4. Februar 2009, 18:31

Samstag 7. Mai 2011, 16:09

Hallo zusammen,

erstmal danke für die Kommentare. Hier mal eine Beschreibung der Aufgabe, die Eure Nachfragen hoffentlich beantwortet:

- Ich betrachte zwei Random Walker und interessiere mich für die Verteilung der Zeiten (Anzahl der Schritte) nach denen sie sich treffen.
- Wegen der Verteilungen, lasse ich die while-Schleife *oft* laufen.
- Das ganze hängt von einer Reihe von Parametern ab - für jeden Parametersatz gibt's ne andere Verteilung.
- Der Inhalt der while-Schleife besteht aus ein paar ifs, whiles und eben dem Erzeugen von Pseudozufallszahlen gemäß zB der Normalverteilung (Daher meine offensichtlich sinnlose Beispielfunktion).

Laut zB http://www.scipy.org/PerformancePython lässt sich Python-Code in einigen Fällen wesentlich beschleunigen -- das käme mir durchaus gelegen. Die ganze Verwaltungsarbeit (Ausgaben erzeugen, Daten sortieren und Co) will ich in Python lassen -- das geht sowieso schnell.

Falls möglich (dazu gerne weitere Kommetare) will ich also die Erzeugung der einzelnen Random-Walk-Zeiten beschleunigen. Meines Erachtens ist das der bottleneck des Prozesses (10^9 Durchläufe der while-Schleife sind durchaus möglich).

Danke und beste Grüße, Tyrax
BlackJack

Samstag 7. Mai 2011, 17:30

@Tyrax: Versuch doch erst einmal das "Meines Erachtens…" im letzten Beitrag durch "Meines Wissens…" zu ersetzen. Messen wie oft was aufgerufen wird und wie viel Zeit es verbraucht.
Benutzeravatar
noisefloor
User
Beiträge: 2977
Registriert: Mittwoch 17. Oktober 2007, 21:40
Wohnort: Görgeshausen
Kontaktdaten:

Samstag 7. Mai 2011, 20:03

Hallo,

und dann vielleicht auch erstmal probieren, was es bringt, die Optimierungen zu nutzen, die Python an sich so bringt (z.B. optimierter Byte-Code).

Ansonsten ist die Funktion nicht sooo komplex. Du kannst sie ja auch mal aus Spaß an der Freunde in anderen Sprachen, die als "schnell" gelten (z.B. C, Lua) zu implementieren und dann misst du, was der Unterschied zu Python ist.

Gruß, noisefloor
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Sonntag 8. Mai 2011, 01:56

noisefloor hat geschrieben:und dann vielleicht auch erstmal probieren, was es bringt, die Optimierungen zu nutzen, die Python an sich so bringt (z.B. optimierter Byte-Code).
Wenn du mit "optimierter Byte-Code" .pyo-Dateien meinst, dann ist die Antwort "nichts", denn .pyo-Dateien sind nicht im Performance-Sinne optimiert, sondern enthalten einfach keine Docstrings.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Tyrax
User
Beiträge: 73
Registriert: Mittwoch 4. Februar 2009, 18:31

Sonntag 8. Mai 2011, 16:18

Hallo,

ich hab' mal durchgezählt. Pro Schleifendurchlauf sind es (im Mittel)
- zwei random.gauss-Aufrufe,
- vier Vergleiche für if/while,
- vier Additionen,
- vier Multiplikationen,
- eine Division.

Also im wesentlichen kommt jede der Aufgaben etwa gleich oft vor. Ich habe den Aufwand der Operationen mal verglichen. Für jeweils 10^6 Berechnungen bekomme ich:

1000000 mal ne leere Funktion mit einer Zuweisung aufrufen dauert 0.416296958923 Sekunden.
1000000 mal ne for-Schleife mit je einem random.gauss-Aufruf durchlaufen lassen dauert 2.10397410393 Sekunden.
1000000 mal ne for-Schleife mit je einer Addition durchlaufen lassen dauert 0.0695428848267 Sekunden.
1000000 mal ne for-Schleife mit je einer Multiplikation durchlaufen lassen dauert 0.0685050487518 Sekunden.
1000000 mal ne for-Schleife mit je einer Division durchlaufen lassen dauert 0.132606983185 Sekunden.

Da ich bei weitem nicht so oft Funktionen aufrufe, wie ich Zufallszahlen ziehe, würde ich also sagen, dass der Aufruf von random.gauss der Knackpunkt ist. Die Division kann ich vielleicht noch loswerden, mal sehen.

Ich werde mal versuchen, die gleichen Sachen in C hinzuschreiben und die Ergebnisse vergleichen. Bis dahin freue ich mich auf weitere Kommentare.

@sma: die import-Anweisung innerhalb der Funktion war nur ein Unfall beim Erstellen des Beispiels. Trotzdem danke für den Hinweis.

Danke und Grüße, Tyrax
Zuletzt geändert von Tyrax am Sonntag 8. Mai 2011, 16:53, insgesamt 1-mal geändert.
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Sonntag 8. Mai 2011, 16:28

Also ``random.gauss(c, d)`` ist doch eh konstant in der Schleife... oder übersehe ich grad das offensichtliche?
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
lunar

Sonntag 8. Mai 2011, 16:50

@Leonidas: Wieso sollte "gauss(c, d)" konstant sein?!
Benutzeravatar
HerrHagen
User
Beiträge: 430
Registriert: Freitag 6. Juni 2008, 19:07

Sonntag 8. Mai 2011, 17:58

@Tyrax: Hast du es mal mit numpy versucht? Damit kannst du gleich Tausende Zufallszahlen auf einmal in Windeseile erzeugen. Wenn ich deine Funktion mal (mehr oder weniger) 1:1 übersetze, komme ich auf folgende Funktion:

Code: Alles auswählen

def dumme_funktion_mal_n(a, b, c, d, n=10000):
  x = numpy.random.normal(a, b, size=n)
  y = numpy.random.normal(c, d, size=n)
  return (x == y).any()
Für n=10000 Wiederholungen braucht diese Funktion 0.004s.
Allerdings werd ich irgendwie aus deiner Aufgabenstellung nicht so recht schlau. Was ist der Nutzen dieser Funktion? Willst du wirklich 10000 mal probieren ob eine normalverteilte Zufallszahl exakt (!) gleich einer anderen ist? Was soll das bringen? Wiilst du nicht eher vergleichen ob die Zufallszahlen in einem bestimmten Bereich liegen?

MFG HerrHagen
BlackJack

Sonntag 8. Mai 2011, 18:08

@HerrHagen: Soweit ich das verstanden habe gibt es zwei "Walker" die zufällige Schritte machen, und wenn die sich Treffen bricht die Schleife ab. Das eigentliche Problem ist also nicht das zwei Zufallszahlen gleich sind, sondern das zwei Folgen von Zufallszahlen zu einem Weg führen der beim gleichen Punkt landet. http://en.wikipedia.org/wiki/Random_walk

Ich verstehe ehrlich gesagt nicht so ganz warum uns nicht das ganze Problem gezeigt wird, sondern nur so ein Ersatz an dem nicht sieht, was denn nun eigentlich genau beschleunigt werden soll, und der deshalb zu solchen Missverständnissen führt. Hier sind ja keine allgemeinen Beschleunigungstechniken gefragt sondern konkret etwas für den vorhandenen aber nicht gezeigten Code. Und das kann man allgemein halt nicht beantworten.
Antworten