Funktionswerte cachen

[Nobot]

Guten morgen

Ich mache mir gerade Gedanken über einen gekapselten Funktionsaufruf. Ich habe eine Funktion (genau zwei), die einen und zwei Parameter haben, allerdings "relativ aufwendig" in der Berechnung sind. Ich habe mir überlegt, daß es wohl sinnvoll wäre einen gewissen Teil der Ergebnisse zu cachen - die Parameterverteilung ist relativ zufällig, man wird aber mehr als die Hälfte der Ergebnisse min. 2x abfragen - teilweise auch mehr.

Es wäre jetzt sehr praktisch, wenn beim ersten Funktionsaufruf das Ergebnis berechnet wird und dann irgendwo gespeichert wird, beim zweiten Aufruf wird dann lediglich das Ergebnis zurückgeliefert. Und ich dachte, daß so die 500 letzten Werte gespeichert werden (oder evtl. die 500 beliebtesten?). Und bei entsprechend mehr Werten ja nach Strategie wieder welche aussortiert - wenn es dann einen Cache Miss gibt, wird neu berechnet.

Während ich mir für die 500 letzten Werte da schon was in etwa vorstellen könnte, würde mich erstmal interessieren, ob es vielleicht sowas schon in fertig und performant gibt? Oder wenn nicht, ob man sowas vielleicht auch in wenigen Zeilen unter Verwendung von STL Container erstellen könnte?

[del_4901]

Tja, ohne das Problem zu kennen würde ich sagen, dass man das Problem so umdesignen (refaktorisieren) kann, dass man so ein Kompliziertes Konstrukt nicht braucht, oder sind die Eingabewerte echt zufällig. Dann ist auch noch die Frage ob die Funktion partiell, total, symetrisch etc. ist.
Bei einer Batchbearbeitung und nicht zufälligen Werte, würde ich die Eingaben einfach vorsortieren, und dann nur neu berechnen, wenn sich die Funktionswerte ändern. Man kann die Funktionserte natürlich auch in eine map einfügen, das geht aber gut auf den Speicher. Wenn der Key in der Map existiert, dann wird der Wert genommen, ansonsten legt man ein neues Key/Wertepaar an.
Um das ganze zu beschränken muss man das am besten irgendwie nach Zugriffen sortieren. Dafür könnte man sich ein Set anlegen, was nach Zugriffen der Werte Sortiert ist, und eine Referenz auf die Funktionswerte besitzt. Dann geht man gelegendlich durch, und sammelt den alten Kladeradatsch ein.

Am schönsten wirds, wenn man das ganz über ein neuronales Netz realisiert, aber da will ich noch nicht klugscheissen, da bin ich grad selber am Informationen sammeln.

[Gast]

Das erinnert mich an mein letztes Numerik-Projekt für die Uni, wo eine Funktion gerne mal 30s in Anspruch nahm. Konnten wir auf 3s drücken und am Ende hatten wir die wichtigsten Funktionsergebnisse einfach in einer Datei drinne stehen, die eingelesen wurde ...

Also ich würde das wie folgt machen:
Funktion in eine extra Klasse kapseln (ggf mit singleton) und dort die Funktion analysieren:
1) Wurde noch nicht berechnet -> Parameter durchreichen und berechnen lassen, Ausgabe abspeichern (entweder nur als Variable oder gar persistent)
2) Wurde schon berechnet -> Ergebnis aus gespeicherter Variable zurückgeben

Wenn jetzt Pi mal Daumen 1% der abgefragten Funktionswerte 99,9% der Abfragen ausmachen und Speicher sehr teuer ist bzw deine "Ergebnisse" sehr groß sind, kannst duch sicher auch nur häufige Nachfragen cachen.
Aber Achtung: "Personen, die sin(3) berechnet haben wollten, fragten auch nach cos(3), exp(3) und sin(3,141526)" hat sich Amazon patentieren lassen (scnr (http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=/netahtml/PTO/search-bool.html&r=1&f=G&l=50&co1=AND&d=PG01&s1=20020198882&OS=20020198882&RS=20020198882))

Probleme kann es geben, wenn die Funktion von nicht übergebenen Werten abhängt (z.B. wenn sie (warum auch immer, ist ein ausgedachtes Beispiel) die Systemzeit zum Ergebniss dazuaddiert -> Rechnungen ^^). Doof ists auch, wenn du als Parameter Gleitkommazahlen hast, davon gibts einfach zu viele! Integer oder String sähe da besser aus.

hth, mfg


(sOT: Wenn du zB AES damit beschleunigen willst, weil du dann schneller verschlüsseln kannst, vergiß es! (http://cr.yp.to/antiforgery/cachetiming-20050414.pdf))

[Arokh]

Offenbar geht es dir um Daten, die nur im Scope einer Funktion sichtbar sein sollen, zwischen den Aufrufen der Funktion aber nicht verloren gehen sollen.
In C++ fallen mir dafür vier Möglichkeiten ein:

1) du verwendest innerhalb der Funktion statische Variablen, in denen du die Ergebnisse gespeichert hältst.

2) du baust eine Klasse um die Funktion herum, und speicherst die Daten in deren Membervariablen.

3) du speicherst die Daten in globalen Variablen. Gilt gemeinhin als unschön bis strafbar ;). Läßt sich aber noch einigermaßen elegant hinbiegen, wenn du der Funktion ne eigene Source-Datei spendierst und die Sichtbarkeit der verwendeten globalen Variablen auf diese Datei beschränkst (geht mit dem Schlüsselwort static).

4) du verlagerst das Ganze vom RAM auf die Festplatte, indem du die Daten innerhalb der Funktion in eine Datei speicherst und bei Bedarf ausliest. Dateizugriffe sind im Vergleich zu RAM-Zugriffen aber teuer.