Brauche Hilfe beim Optimieren

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.
Benutzeravatar
The Honk
User
Beiträge: 15
Registriert: Montag 22. September 2008, 15:38

Brauche Hilfe beim Optimieren

Beitragvon The Honk » Mittwoch 24. September 2008, 19:17

Da das Gesamte Programm etwas komplexer ist versuche ich mich nur auf das wichtigste zu beschränken.
Ich habe eine Funktion die Gesamtlaenge mehrerer Kanten (zwischen zwei Punkten) zurück geben soll. Das Problem ist, dass die kleine Funktion viel zu langsam läuft. In der Laufzeitanalyse sieht das so aus:

Gesamtlaufzeit: 23.367 sec
Laufzeit der Funktion: 16.757 sec bei 866854 Aufrufen

Wenn die Anzahl der Aufrufe reduziert werden kann schaff ich das alleine, das Problem liegt woanders:
Alle Kanten und ihre Längen sind bereits in einer Matrix abgespeichert.
Der Funktion können allerdings nur Punkte übergeben werden (das hat einen bestimmten Grund auf den ich nicht näher eingehen möchte). Der (bereits optimierte) Zugriff von den beiden Punkten auf ihre dazugehörige Kante dauert länger als die Neuberechnung des Absandes der Punkte. Die Funktion brauch nun deshalb so lange, weil für ein und dieselbe Kante mehrmals die Länge berechnet wird. Ich müsste eigentlich den Abstand zwischen zwei Punkten berechnen, abspeichern und beim erneuten Auftreffen auf die selben Punkte den abgespeicherten Wert benutzen.
Nun fällt mir keine elegante Lösung ein die das Problem auf diese Weise optimaler Lösen könnte.

Code: Alles auswählen

    def matchinglaenge(self,punkte):
        geslaenge=0
        for nummer in xrange(1, len(punkte),2):
            punkt1=punkte[nummer]
            punkt2=punkte[nummer-1]
            geslaenge+=((punkt2.x-punkt1.x)**2+(punkt2.y-punkt1.y)**2)**0.5
        return geslaenge
Dem Weisen gilt Schweigen als Antwort
BlackJack

Beitragvon BlackJack » Mittwoch 24. September 2008, 20:13

Du könntest vielleicht ein Dictionary anlegen, das Punkte auf die Strecke abbildet und dort erst nachschauen ob's dafür schon einmal eine Berechnung gab. Wenn ja, Ergebnis aus dem Dictionary holen, wenn nein, Ergebnis berechnen und im Dictionary speichern.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Mittwoch 24. September 2008, 20:39

Wenn für Zeile 8 die Funktion hypot() aus dem math-Modul verwendest, wird das ganze ca. 30% schneller:

Code: Alles auswählen

import math
# ...
geslaenge += math.hypot(punkt2.x-punkt1.x,punkt2.y-punkt1.y)
# ...


Zum Vorschlag von BlackJack: Wenn die Koordinaten der Punkte Fließkommawerte sind, dann müsstest du natürlich sicher sein, dass gleiche Punkte auch wirklich gleich sind. Bei ganzzahligen Koordinaten ist das unproblematisch.
Bedenken müsste man dabei aber auch, dass für die Länge der Kante die Reihenfolge der beiden Punkte unerheblich ist, so dass man überlegen könnte, als Schlüssel für das Dictionary ein frozenset zu verwenden.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Donnerstag 25. September 2008, 11:26

Ich könnte mir vorstellen, dass die folgende Schleife effizienter (in jedem Fall aber eleganter) ist, als der Index-Zugriff auf die Liste:

Code: Alles auswählen

i = iter(punkte)
for p1 in i:
    p2 = i.next()
    print p1, p2

Ob's was bringt, habe ich nicht ausprobiert.
Stefan
Lonestar
User
Beiträge: 147
Registriert: Samstag 9. August 2008, 08:31

Beitragvon Lonestar » Donnerstag 25. September 2008, 11:59

@sma
du machst aber nicht das gleiche wie er mit seinem xrange(). In seiner variante mit der Schleife ruft er nur jedes 2. Element auf und rechnet. du rufst jedes Element auf und rechnest Werte aus die nicht interessieren. Deine Variante sieht zwar eleganter aus ist aber nur halb so schnell.
Benutzeravatar
The Honk
User
Beiträge: 15
Registriert: Montag 22. September 2008, 15:38

Beitragvon The Honk » Donnerstag 25. September 2008, 12:07

da hat er recht.
@sma
bei mit sind es dauert es 1sec laenge (das sind zwar nur 1/16 der laufzeit des funktion laenger aber es ist zu viel)

@numerix
deine lösung macht die funktion leider um über 100% langsamer

trotzdem danke für die hilfe
Dem Weisen gilt Schweigen als Antwort
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Beitragvon audax » Donnerstag 25. September 2008, 12:17

mach es eben in Pyrex...
Benutzeravatar
The Honk
User
Beiträge: 15
Registriert: Montag 22. September 2008, 15:38

Beitragvon The Honk » Donnerstag 25. September 2008, 12:21

noch nie gehört
Dem Weisen gilt Schweigen als Antwort
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Donnerstag 25. September 2008, 13:24

audax hat geschrieben:mach es eben in Pyrex...

Würde wohl eher zu Cython raten.

Hint: Suchmaschinen existieren.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Beitragvon rayo » Donnerstag 25. September 2008, 13:46

oder mit psyco probieren.

Code: Alles auswählen

import psyco
psyco.full()


vielleicht reichts dann schon.
Benutzeravatar
The Honk
User
Beiträge: 15
Registriert: Montag 22. September 2008, 15:38

Beitragvon The Honk » Donnerstag 25. September 2008, 14:39

mit spyco hab ich von 2823318 16funktionsafurufe weniger
trotzdem bleibt das programm gleich schnell bzw. wird sogar ein klein wenig langsamer

Cython hab ich noch nicht ausprobiert, aber so wie es klingt müsste ich mich damit mit C auskennen, was ich nun gar nicht kann
Dem Weisen gilt Schweigen als Antwort
CM
User
Beiträge: 2464
Registriert: Sonntag 29. August 2004, 19:47
Kontaktdaten:

Beitragvon CM » Donnerstag 25. September 2008, 14:50

Schau mal in diesen Thread: http://www.python-forum.de/topic-12120.html

Inzwischen habe ich eine C-Version (erste Funktion, in die Doppelschleife gehen). Das kann Dir ggf. als Template dienen.

HTH
Christian
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Donnerstag 25. September 2008, 15:04

The Honk hat geschrieben:@numerix
deine lösung macht die funktion leider um über 100% langsamer


Ich habe - vor meinem Post - ein entsprechendes Szenario mit 500.000 zufälligen Punkten erstellt und jeweils die Zeit für die Berechnung der Längen gemessen. Bei Fließkommakoordinaten erreiche ich damit eine ca. 25%-30% schnellere Berechnung, mit Integerkoordinaten bringt es allerdings deutlich weniger. 100% LANGSAMER kann ich mir nicht erklären.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Donnerstag 25. September 2008, 15:05

The Honk hat geschrieben:Cython hab ich noch nicht ausprobiert, aber so wie es klingt müsste ich mich damit mit C auskennen, was ich nun gar nicht kann

Nein, Cython kompiliert eine Python-ähnliche Sprache zu einem C-Modul, welches dann als Erweiterungsmodul für CPython genutzt werden kann.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Donnerstag 25. September 2008, 15:55

@Honk: Was ist denn mit deiner Idee, einmal berechnete Kanten nicht wieder zu verwenden, sondern beim auftauchen des gleichen Punktpaares den bereits berechneten Wert nur abzurufen? Hast du das inzwischen ausprobiert?

Ob das viel bringt, dürfte letztlich davon abhängen, wie häufig dieser Fall eintritt. Kannst du das prozentual abschätzen (also etwa in 50% der Fälle o.ä.) Aus welchem Wertebereich stammen denn die Koordinaten? Und sind sie ganzzahlig oder Fließkommawerte?

Dann würde ich versuchen, das mal mit Zufallswerten zu simulieren und sehen, ob es was bringt.

Was die Sache mit dem hypot() angeht: Bei meinen Versuchen hatte ich mit Koordinaten-Tupeln statt - wie bei dir - mit Punkt-Objekten gearbeitet. Ich habe dann die Tupel mal durch Punkt-Objekte ersetzt und festgestellt, dass die hypot()-Variante dann minimal langsamer ist als deine ursprüngliche Fassung.

Insgesamt war es mit Tupeln etwas schneller als mit Punkt-Objekten. Kannst du darauf Einfluss nehmen, oder müssen es Punkt-Objekte sein, die zur Längenmessung angeliefert werden?

Wenn ich nichts übersehe, dann wären Koordinatentupel auch für die Idee "Wiederabrufen schon berechneter Kantenlängen" deutlich vorteilhafter.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder