Brauche Hilfe beim Optimieren

[The Honk]

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

[BlackJack]

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.

[numerix]

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]

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]

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

[The Honk]

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

[audax]

mach es eben in Pyrex...

[The Honk]

noch nie gehört

[Leonidas]

mach es eben in Pyrex...

Würde wohl eher zu Cython raten.

Hint: Suchmaschinen existieren.

[rayo]

oder mit psyco probieren.

Code: Alles auswählen

import psyco
psyco.full()

vielleicht reichts dann schon.

[The Honk]

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

[CM]

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

[numerix]

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

[Leonidas]

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.

[numerix]

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

[The Honk]

ich kam noch nicht dazu das mit gespeicherten laengen auszuprobieren.
Zu den Punktobjekten: ja ich brauch welche, denn in den Objekten ist neben der x- und y-koordinate und einigen weiteren integerwerten eine Liste mit (bestimmten) Kanten gespeichert die an dem Punkt münden. Die Kanten von denen ich die Laenge brauche sind nicht im Punkt gespeichert.

[numerix]

Ich habe das jetzt mal ausprobiert mit der Wiederverwendung zuvor bereits berechneter Kantenlängen. Bringt nix!

Selbst bei einer Wiederverwendungsquote von ca. 90% braucht diese Variante doppelt so lange wie deine ursprüngliche. Wie BlackJack in seinem Post schon geäußert hat, kommt dafür eigentlich nur ein Dictionary in Frage. Das braucht aber einen vernünftigen Schlüssel und m.E. kann man dafür eigentlich nur ein frozenset gebrauchen, damit der Abstand d(p1,p2) = d(p2,p1) ebenfalls erkannt und verwendet wird.

Das Erzeugen der Koordinatentupel und frozensets, das Prüfen, ob der Schlüssel schon im Dictionary ist und ggf. dann doch die Neuberechnung und Aufnahme in das Dictionary dauert dann aber viel zu lange.

[bords0]

Ich habe das jetzt mal ausprobiert mit der Wiederverwendung zuvor bereits berechneter Kantenlängen. Bringt nix!

Selbst bei einer Wiederverwendungsquote von ca. 90% braucht diese Variante doppelt so lange wie deine ursprüngliche. Wie BlackJack in seinem Post schon geäußert hat, kommt dafür eigentlich nur ein Dictionary in Frage. Das braucht aber einen vernünftigen Schlüssel und m.E. kann man dafür eigentlich nur ein frozenset gebrauchen, damit der Abstand d(p1,p2) = d(p2,p1) ebenfalls erkannt und verwendet wird.

Wenn man d(p1,p2) und d(p2,p1) getrennt abspeichert, klappt die Beschleunigung doch prima (matchinglaenge2()):

Code: Alles auswählen

import random
import timeit

class Punkt(object):
    def __init__(self):
        self.x = random.random()
        self.y = random.random()

def matchinglaenge(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


def dist(p, q):
    return ((p.x - q.x) ** 2 + (p.y - q.y) ** 2) ** 0.5

class DistDict(dict):
    def __missing__(self, key):
        v = self[key] = dist(*key)
        return v

def matchinglaenge2(punkte, d=DistDict()):
    return sum(d[k] for k in zip(punkte[::2], punkte[1::2]))

def dummy(punkte):
    return sum(p.x - p.y for p in punkte)

if __name__ == "__main__":
    punkte = [Punkt() for i in range(10000)]
    print timeit.Timer("matchinglaenge(punkte)", "from __main__ import matchinglaenge, punkte").timeit(10)
    print timeit.Timer("matchinglaenge2(punkte)", "from __main__ import matchinglaenge2, punkte").timeit(10)
    print timeit.Timer("dummy(punkte)", "from __main__ import dummy, punkte").timeit(10)

Ergibt bei mir:

Code: Alles auswählen

0.102954635296
0.0588070550866
0.0600593790552

Immerhin auch schneller als die dummy()-Funktion, die i.W. nur die Attribute x und y nachschlägt.

[The Honk]

Code: Alles auswählen

return sum(d[k] for k in zip(punkte[::2], punkte[1::2]))

Danke, das ist genial und ich kannte es noch nicht. Ich werds verwenden.

[numerix]

Wenn man d(p1,p2) und d(p2,p1) getrennt abspeichert, klappt die Beschleunigung doch prima (matchinglaenge2()):

Nein, klappt nicht.
Dein Code enthält interessante Elemente, z.B. die von dict abgeleitete Klasse, aber erstens funktioniert es nicht so, wie es vorgibt zu funktionieren, und zweitens ist es weniger als halb so schnell.

zu 1.: Durch das zip() werden jeweils zwei Punktobjekte als Tupel verpackt und als Schlüssel für das Dictionary gesetzt. Da vorher lauter unterschiedliche Punktiobjekte erzeugt wurden, gibt es niemals einen Schlüssel, der bereits vorhanden war. Dazu müssten die Koordinaten, nicht die Punktobjekte verglichen werden. Faktisch wird also in JEDEM Fall die __missing__()-Methode mit der Berechnung des Abstandes aufgerufen.

zu 2.: siehe Code (das ist deiner, nur leicht umgestellt und mit geänderter Zeitmessung):

Code: Alles auswählen

import random
import time

def dist(p, q):
    return ((p.x - q.x) ** 2 + (p.y - q.y) ** 2) ** 0.5

class Punkt(object):
    def __init__(self):
        self.x = random.randrange(3)
        self.y = random.randrange(3)

class DistDict(dict):
    def __missing__(self, key):
        v = self[key] = dist(*key)
        return v

def matchinglaenge(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

def matchinglaenge2(punkte, d=DistDict()):
    return sum(d[k] for k in zip(punkte[::2], punkte[1::2]))

punkte = [Punkt() for k in xrange(100000)]

t0 = time.time()
matchinglaenge(punkte)
print time.time()-t0

t0 = time.time()
matchinglaenge2(punkte)
print time.time()-t0

Ergibt bei mir:

Code: Alles auswählen

0.256042957306
0.674798965454