Memoization Libraries für C?

Question

Bei einem Projekt, an dem ich gerade arbeite, gibt es eine Reihe von Zuständen, bei denen Berechnungen zuverlässig die gleichen Ergebnisse liefern (und keine Nebenwirkungen haben). Die offensichtliche Lösung wäre, Memoisierung für alle kostspieligen Funktionen zu verwenden.

Ich bräuchte eine Memoisierung, die mehr als einen Zustand behandelt (so dass ich einen Cache-Satz ungültig machen könnte, ohne einen anderen ungültig zu machen). Kennt jemand eine gute C-Bibliothek für diese Art von Dingen? (Beachten Sie, dass es sich nicht um C++ handeln kann, sondern um C.)

Ich habe mit einigen guten Implementierungen in Python gearbeitet, die Dekoratoren verwenden, um eine Reihe von verschiedenen Funktionen flexibel zu memoisieren. Ich frage mich irgendwie, ob es eine generische Bibliothek gibt, die ähnliche Dinge mit C tun könnte (obwohl wahrscheinlich mit expliziten Funktion Wrapping statt bequemer Syntax). Ich denke nur, es wäre dumm zu haben, um Caching zu jeder Funktion einzeln hinzufügen, wenn es ein gemeinsames genug Problem gibt es einige off-the-shelf-Lösungen für sie sein muss.

Die Merkmale, auf die ich achten würde, sind die folgenden:

1. Kann Funktionen mit verschiedenen Arten von Eingaben und Ausgaben zwischenspeichern
2. Verwaltet mehrere verschiedene Zwischenspeicher (so dass Sie kurzfristige und langfristige Zwischenspeicher haben können)
3. Hat gute Funktionen zum Ungültigmachen von Caches
4. Zur Verwendung durch Umhüllung von Funktionen gedacht, anstatt bestehende Funktionen zu ändern

Kennt jemand eine C-Implementierung, die alle oder die meisten dieser Anforderungen erfüllen kann?

Answer 1

Okay, da es keine Memoisierungsbibliotheken für C gab und ich nach einer Drop-in-Lösung für die Memoisierung bestehender C-Funktionen in einer Codebasis suchte, habe ich meine eigene kleine Memoisierungsbibliothek erstellt, die ich unter der APL 2.0 freigebe. Ich hoffe, dass die Leute sie nützlich finden und dass sie auf anderen Compilern nicht abstürzt und verbrennt. Wenn es Probleme gibt, können Sie mir hier eine Nachricht zukommen lassen, und ich werde mich darum kümmern, sobald ich die Zeit dazu habe (was wahrscheinlich in Monatsschritten gemessen wird).

Diese Bibliothek ist nicht auf Geschwindigkeit ausgelegt, aber sie funktioniert und wurde getestet, um sicherzustellen, dass sie recht einfach zu benutzen ist und bei meinen Tests keine Speicherlecks aufweist. Im Grunde kann ich damit Funktionen ähnlich dem Dekorator-Muster, das ich aus Python kenne, eine Memoisierung hinzufügen.

Die Bibliothek ist derzeit auf SourceForge als C-Memo Bibliothek . Es wird mit einem kleinen Benutzerhandbuch und einer Reihe von Bibliotheken von Drittanbietern geliefert, die für generisches Hashing lizenziert sind. Wenn sich der Standort ändert, werde ich versuchen, diesen Link zu aktualisieren. Ich fand dies hilfreich bei der Arbeit an meinem Projekt, hoffentlich werden andere es für ihre Projekte nützlich finden.

Answer 2

Memoisierung ist quasi in die Haskell-Sprache eingebaut. Sie können diese Funktionalität von c aus aufrufen

Aktualisierung:
Ich bin immer noch dabei, etwas über funktionale Programmierung zu lernen, aber ich weiß, dass Memoisierung in der funktionalen Programmierung ziemlich verbreitet ist, weil die Sprachfunktionen es einfach machen. Ich lerne gerade f#. Ich kenne Haskell nicht, aber es ist die einzige funktionale Sprache, die ich kenne, die mit C interagiert. Vielleicht finden Sie eine andere funktionale Programmiersprache, die eine geeignetere Schnittstelle zu C bietet als Haskell.

Answer 3

Warum, kann C++ einfach nicht sein?

Als Ausgangspunkt können Sie sich diese Memoisierungsfunktion ansehen:

Erklärung:

template<typename T, typename F>
auto Memoize(T key, F function) {
  static T memory_key = key;
  static auto memory = function(memory_key);
  if (memory_key != key) {
    memory_key = key;
    memory = function(memory_key);
  }

  return memory;
}

Beispiel für die Verwendung:

auto index = Memoize(value, IndexByLetter);