Brauche Hilfe beim Optimieren

[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

[The Honk]

1. ich habs auch selber ausprobiert, mit dem dictionary war es bei mir 400% langsamer als ohne

2. Die Zeile:

Code: Alles auswählen

return sum(d[matching] for matching in matchings)

macht das ganze nochmal langsamer als einfach:

Code: Alles auswählen

for matching in matchings:
    summe+=d[matching]
return summe

3. Es gibt sogar relativ oft einen Schlüssel der bereits im dic steht: Bei 151498 matching_laenge Aufrufen wird nur 125-mal die methode __missing__ aufgerufen, daran liegt es also nicht.

4. Von 15.287sec gehen 14.930sec tatsächlich an die funktion matching_laenge und nicht an untergeordnete (sum(...) wurde bereits in eine "normale" Schleife umgewandelt)

[audax]

Code: Alles auswählen

from itertools import izip, starmap, islice


def matchinglaenge2(punkte):
    return sum(starmap(dist, 
                izip(islice(punkte, None, None, 2),
                     islice(punkte, 1, None, 2))))

->
0.0830249786377
0.087110042572

Man sollte also einfach "dist" auslagern und in C implementieren.

€dit:
Grad getestet, bring nichts.

[The Honk]

Nun, eigentlich hatte ich nicht vor, irgendwas in C auszulagern bzw. irgendetwas anderes als das Standart Python zu verwenden (also kein Cython/Pyrex usw.), da ich das Programm auch noch Leuten vorstellen muss, für die es besser ist, dass der Code so einfach wie möglich zu erklären ist.

[audax]

Code: Alles auswählen

import random
import time
from dist import matching
from itertools import izip, starmap, islice
from operator import itemgetter

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

class Punkt(tuple):
    __slots__ = ()
    def __new__(cls):
        return tuple.__new__(cls, (random.randrange(3), random.randrange(3)))

    x = property(itemgetter(0))
    y = property(itemgetter(1))

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):
    return sum(starmap(dist, 
                izip(islice(punkte, None, None, 2),
                     islice(punkte, 1, None, 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


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

dist.pyx

Code: Alles auswählen

cdef double dist(double a_x, double a_y, double b_x, double b_y):
    return ((a_x - b_x) ** 2 + (a_y - b_y) ** 2) ** 0.5

def matching(punkte):
    cdef double total = 0
    cdef double a_x, a_y, b_x, b_y
    for x from 1 <= x < len(punkte):
        a_x, a_y = punkte[x]
        b_x, b_y = punkte[-1]
        total += dist(a_x, a_y, b_x, b_y)
    return total

Setup.py

Code: Alles auswählen

from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext

setup(
  name = 'perf',
  ext_modules=[ 
    Extension("dist",       ["dist.pyx"]),
    ],
  cmdclass = {'build_ext': build_ext}
)

Zeiten:
0.116365909576
0.120131969452
0.0580198764801
[/code]

[numerix]

Was es alles gibt!

Könntest du erläutern, warum du die Klasse Punkt auf diese Weise implementiert hast?

[audax]

Weil man Tupel sehr schnell "entpacken" kann, also:

Code: Alles auswählen

x, y = point

womit man dann fix rechnen kann. Indizieren ist in Python relativ langsam. Außerdem sind die Dinger immutable und wir brauchen sie ja nicht mutable.

"point.x" geht jetzt trotzdem noch, allerdings mit dem Overhead eines Funktionsaufrufs, und zwar itemgetter(0)(self). Aber solange wir fast immer entpacken ist das ok

[numerix]

Danke für die Erläuterung!

Ich habe noch weiter experimentiert und - siehe da - auch ohne Griff in die C-Kiste lässt sich noch was herausholen, wenn man deine intelligente Punkt-Klasse verwendet:

Code: Alles auswählen

import random
import time
from operator import itemgetter

class Punkt(tuple):
    __slots__ = ()
    def __new__(cls):
        return tuple.__new__(cls, (random.randrange(3), random.randrange(3)))
    x = property(itemgetter(0))
    y = property(itemgetter(1))

def distance(p, q):
    return ((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2) ** 0.5

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

def matchinglaenge1(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]))

def matchinglaenge3(punkte):
    dist = {}
    geslaenge = 0
    for k in xrange(0,len(punkte),2):
        pair = punkte[k], punkte[k+1]
        try:
            laenge = dist[pair]
        except KeyError:
            dist[pair] = laenge = distance(*pair)
        geslaenge += laenge
    return geslaenge

# ----------

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

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

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

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

Ergibt bei mir:

Code: Alles auswählen

0.117043972015
0.140959978104
0.0497407913208

Anmerkungen:

Die Variante (nicht im Code, weil ineffizient) mit frozensets bringt nichts; zwar kann man dann noch öfter auf die schon berechneten Kantenlängen zurückgreifen, aber die Erzeugung und das Arbeiten mit den Mengen kostet mehr Zeit, als man damit gewinnt.

Wenn man in der Funktion des OP den Zugriff über die Tupel-Indizes statt über die Objektattribute vornimmt, wird es ebenfalls ein ganzes Stück schneller.

Die Variante mit dem zip() funktioniert mit dieser Klassendefinition jetzt auch, weil Klassenobjekte eben auch Tupel sind.

Allerdings: So wie ich Honk verstanden habe, hat er keinen Einfluss auf die Punkt-Klasse, so dass diese eben nicht von Tupeln abgeleitet werden und kein Zugriff über Indizes möglich ist. Damit ist der Performance-Gewinn durch die intelligente Klassendefinition wieder dahin.

[The Honk]

in begrenzten Maße habe ich Einfluss auf die Klasse "Punkt", das umstruckturieren kostet allerdings einigen Aufwand. Trotzdem denke ich werde ich die Methode mit den Tupel ausprobieren weil ich auch sehr schön finde (und vor allem weil sie schneller ist).

[bords0]

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):

zu 1.: Ich war der Meinung, dass die Punktobjekte wiederverwendet werden, nicht nur die Koordinaten. Unten bestätigt The Honk, dass __missing__ tatsächlich fast nie aufgerufen wird, d.h. es funktioniert.

zu 2.: Das ist natürlich das Ergebnis davon, wenn man keine Berechnung wiederverwenden kann. Das machst dein Beispiel. Ich hatte auf 90% wiederverwendung geachtet (wie es schon jemand versucht hatte). Ich habe deinen Code minimal verändert, so dass es wieder 90% Wiederverwendung sind.

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)*1.0
        self.y = random.randrange(3)*1.0

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)]*10

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.108999967575
0.061999797821

Dabei ist auch wichtig, dass die Koordinaten floats sind, keine integer. (Obwohl mir unklar ist, warum dist mit integern so viel schneller ist - ich hätte den overhead für Python viiiel größer als den Aufwand für die eigentliche Rechenarbeit eingeschätzt.)

[numerix]

Wie auch immer es sich mit den Punktobjekten nun verhält, auf meinem (etwas betagten) Rechner liefert dein letztes Programm folgende Zeiten:

Code: Alles auswählen

2.96109294891
10.8841571808

Ergo: Es ist ganz offensichtlich auch abhängig von der konkreten Hardware und/oder dem Betriebssystem und/oder der verwendeten Python-Version und/oder ..., welche Variante die schnellere ist.