Memoize Decorator

[NiklasRosenstein]

Hallo,

Ich habe vor einiger Zeit meinen eigenen Memoize decorator entworfen und hätte gerne erfahren was ihr dazu sagt. Was kann man an dem Code noch verbessern ? Danke.

Code: Alles auswählen

 
def memoize(steps=25):
    results = {'args':[],'result':[]}
    def wrapper(f):
        def nf(*args,**kwargs):
            if (args,kwargs) in results["args"]:
                return results["result"][results["args"].index((args,kwargs))]
            else:
                results["args"].append((args,kwargs))
                r = f(*args,**kwargs)
                results["result"].append(r)
                if len(results["result"]) > steps:
                    del results["args"][0]
                    del results["result"][0]
                return r
        nf.__name__ = f.__name__
        return nf
    return wrapper

Cheers,
Niklas

[pillmuncher]

Ich hab's auf Easier to Ask Forgiveness than Permission umgestellt:

Code: Alles auswählen

from functools import wraps
from itertools import cycle

def memoize(steps=25):
    where = cycle(xrange(steps))
    history = [None] * steps
    results = [None] * steps
    def wrapper(f):
        @wraps(f)
        def nf(*args,**kwargs):
            try: # EAFP
                return results[history.index((args,kwargs))]
            except ValueError:
                r = f(*args,**kwargs)
                i = where.next()
                history[i] = args,kwargs
                results[i] = r
                return r
        return nf
    return wrapper

Das läuft ab spätestens Python 2.5.4, ältere Versionen konnte ich nicht testen, weil ich keine installiert habe.

Das habe ich geändert:

• EAFP eingebaut, also einfach ausprobieren und ggf. eine Exception abfangen. Das ist in Python sehr billig und deswegen ein verbreitetes Idiom.
• functools.wraps() verwendet. Damit wird nicht nur der Name, sondern zB. auch der docstring der dekorierten Funktion übernommen.
• Das dict mit den zwei Listen habe ich durch die zwei Listen selbst ersetzt. Die Namen habe ich angepasst.
• Die Listen verwende ich als ring buffer. Alle Anfüge-Operationen sind dann O(1) statt O(n).

Eine Anmerkung zu deinem Code. Die Zeilen:

Code: Alles auswählen

                results["args"].append((args,kwargs))
                r = f(*args,**kwargs)
                results["result"].append(r)

sollten so aussehen:

Code: Alles auswählen

                r = f(*args,**kwargs)
                results["args"].append((args,kwargs))
                results["result"].append(r)

denn wenn in f eine Exception fliegt, wird bei dir zwar results["args"] geändert, aber nicht results["result"]. Bei den nachfolgenden Aufrufen kommt es dann zu unerwarteten Fehlern:

Code: Alles auswählen

@memoize(3)
def foo(x):
    if x == 3:
        raise Exception
    return x
print foo(1)
print foo(2)
try:
    print foo(3)
except:
    print 'oops!'
print foo(4)
print foo(4) # <-- hier krachts

Ergebnis:

1
2
oops!
4
Traceback (most recent call last):
  File "memoizing.py", line 32, in <module>
    print foo(4) # <-- hier krachts
  File "memoizing.py", line 6, in nf
    return results["result"][results["args"].index((args,kwargs))]
IndexError: list index out of range

Gruß,
Mick.

[cofi]

Der vollständigkeit halber: Ab Python 3.2 gibt es den LRU-Decorator frei haus: http://docs.python.org/py3k/library/fun ... .lru_cache

[Xynon1]

Entschuldigt meine Unwissenheit, aber ab wann lohnt sich so ein Dekorator ?
Mir ist zwar klar das es einem nur etwas nützt wenn häufig die Funktion aus den selben Parameter häufig die selben Ergebnisse berechnen muss. Bei I/O-Operation sicher praktisch. Aber ab welcher Durchlaufgeschwindigkeit pro Ruf sollte man sowas in Erwägung ziehen? Bei einer einfachen Funktion wie "add" wo ich nur Einsen und Nullen addiere wird sich sowas wohl kaum lohnen.

Ich kannte dieses Prinzip bisher nicht, aber ich überlege gerade ob sich das bei meinen "draw"-Funktion in meiner pygame GUI lohnt. Da das ständige "blitten" nun doch relativ Performance-Aufwendig ist und dennoch meistens immer wieder die gleichen Surfaces erzeugt werden. Diese werden ja nur durch eine Benutzereingabe verändert und zur Zeit überlege ich wie ich am besten ein System aufbaue welches immer erst bei einer Eingabe einen Neuberechnung auslöst. Das funktioniert aber immer nur vom obersten Widget nach unten hin und so kann es kommen das dennoch häufig das selbe "geblittet" wird. Könnte sich ein solches Zwischenspeichern der Werte für etwas mehr Performance sorgen?
Ist aber bisher nur eine Überlegung, noch habe ich keine Probleme mit der Performace, ich möchte nur ein paar Möglichkeiten im Hinterkopf behalten.

[NiklasRosenstein]

@pillmuncher:
Ehm, EAFP muss ich erstmal googlen ? Nie zuvor gehört.
Aber Wow, danke !
Ich kannte einiges noch garnicht.
Zum Beispiel dachte ich das eine yield-funktion auch sofort ausgewertet wird, also müsste man bei einer eigentlichen Endlosschleiffe auch mit einem Generator in eine Endlosschleife laufen, aber das is garnicht so. Sehr praktisch.

Eine Anmerkung zu deinem Code. (...) Bei den nachfolgenden Aufrufen kommt es dann zu unerwarteten Fehlern:

Da hab ich aber n Schmarrn geschrieben. Danke


@Xynon:
Bei einer Simulation mit aufwendigen berechnungen zum Beispiel.
Oder, wie du sagst, beim blitten wenn doch eh meistens das gleiche immerwieder geblittet wird.
Du musst halt darauf achten, dass der Vergleich der Argumente auch wirklich True ergibt, wenn das selbe wie sonst geblittet wird.
ich kenne mich bei PyGame nicht so aus, nur mal eine in Python entworfene Partikelsimulation darauf visualisiert.

[Xynon1]

@NiklasRosenstein, pillmuncher
Ich wollte euch nur Informieren, das ich die "memoize"-Funktion mit in mein Programm übernommen habe. Ich hoffe es ist okay für euch wenn ich diese dort unter der GNU GPL v.3 veröffentlicht habe. Eure Forennamen und den Link auf diesen Thread habe ich mit beigefügt. Sollte einer von euch Einwände haben werde ich das natürlich ändern.

Wie sieht das hier im Forum im rechtlichen Sinne eigentlich allgemein aus? Also welcher Lizenz sind die Snippets unterworfen wenn keine genannt wird. Unterliegt dann alles der WTFPL oder wie ist das zu verstehen?

[derdon]

Naja, wenn keine Lizenz angegeben wurde, kann man auch nicht von Open Source sprechen. Nur weil jeder die *Möglichkeit* hat, diesen Code zu kopieren, hat noch lange nicht jeder die *Rechte* dazu. Die Rechte zum Kopieren, Verändern, Vervielfältigen etc. müssen explizit gegeben sein, damit sie gelten. Also geposteter Code ist hier auf keinen Fall automatisch WTFPL; wie kommst du auch zu der Annahme? Wer Missverständnisse und Probleme a priori verhindern möchte, kann ja in seiner Signatur schreiben, was er zu seinen Snippets erlaubt / unter welcher Lizenz er den Code veröffentlicht haben möchte.

Aber: IANAL und auch kein Experte.

[Xynon1]

...ist hier auf keinen Fall automatisch WTFPL;

Das habe ich auch nicht erwartet, allerdings hat der Autor auch kein Copyright erhoben, was soweit ich weiß notwendig ist. Aber unter irgendeiner Lizenz müssen die Texte ja stehen, oder?
Deswegen habe ich hier ja nochmal geschrieben und hoffe das keiner etwas gegen die GPL hat. - würde mich doch sehr wundern. Wenn doch ändere ich den Eintrag natürlich umgehend.

[EyDu]

Ich würde mal behaupten, dass der meiste Code hier so kurz und trivial ist, dass keine Angaben gemacht werden müssen.

[lunar]

@Xynon1: Einem Werk im Sinne des UrhG kommt automatisch Urheberrechtsschutz zu, ohne das der Urheber dieses Werks diesen Schutz explizit einfordern oder verlangen müsste. Die "Copyright (c) ..."-Zeilen in Lizenztexten und Programmquellen sind nach deutschem Recht überflüssig, und nur ein Relikt aus der Vergangenheit des us-amerikanischen Rechts. Selbst in den USA haben sie seit Jahrzehnten keinerlei rechtliche Bedeutung mehr.

Ein Programm muss allerdings die Voraussetzungen des UrhG erfüllen, um als Werk zu gelten und Urheberrechtsschutz zu genießen. Dazu zählt insbesondere eine gewisse Schöpfungshöhe. Die dürfte bei den meisten kurzen Programmtexten gar nicht gegeben sein.

Ansonsten gilt halt gar keine Lizenz, wenn keine angegeben ist. Eine Lizenz gewährt dem Lizenznehmer einfache oder ausschließliche Nutzungsrechte am geschützten Programm, aber dessen Urheber ist ja nicht verpflichtet, Rechte zu gewähren. Man kann ein Programm auch ohne Lizenz veröffentlichen. Dann darf es halt nur angesehen, aber weder kopiert, noch ausgeführt noch irgendwie geändert werden.

Das Urheberrecht ist im Übrigen kein Geheimnis, und steht dem interessierten Leser offen

[Xynon1]

Letzteres hatte ich auch so angenommen und ich muss das definitiv mal lesen. Dennoch werde ich die beiden als Autoren des Dekorators nennen, vorraus gesetzt sie haben nichts dagegen. Das finde ich zumindest als angebracht auch wenn man sich das relativ einfach selbst zusammenschreiben kann, aber ich habe es immerhin unverändert übernommen.

[Leonidas]

Entschuldigt meine Unwissenheit, aber ab wann lohnt sich so ein Dekorator ?

Ab dann wenn du sonst eine Berechnung ganz oft wiederholen würdest. Etwa eine naive Fibonacci-Implementation. Oder wo ich für eine Aufgabe irgendwelche Summen in einem Pascalschen Dreieck berechnet habe, da hat Memoization mir Tausende von Funktionsaufrufen gespart. In Python ist die grenze allerdings höher als in vielen anderen Sprachen, weil Funktionsaufrufe relativ gesehen teurer sind, als etwa in funktionalen Sprachen.

[Xynon1]

Das hatte ich eigentlich bereits soweit verstanden und auch verwendet, zwar nicht bei Sachen die besonders häufig aufgerufen werden, aber bei einer Funktion deren Aufruf verhältnismäßig sehr teuer ist. Der Vorteil ist minimal aber vorhanden. Genau genommen speichere ich so generierte Surfaces zwischen, die ich öfters benötige.