Wie LFU-Cache mit STL zu implementieren?

Question

Ich versuche, LFU (Least Frequently Used) -Cache mit reiner STL zu implementieren (ich möchte Boost nicht verwenden!).

Anforderungen sind:

• Assoziative Zugriff auf jedes Element mit std::map ein Key dergleichen.
• Möglichkeit, den Artikel mit der niedrigsten Priorität freizugeben (unter Verwendung seines UsesCount Attributs).
• Möglichkeit, die Priorität (UsesCount) eines beliebigen Elements zu aktualisieren.

Die Probleme sind:

• Wenn I std::vector als Behälter der Elemente verwenden (Key, Value, UsesCount), std::map als Behälter von Iteratoren zum Vektor für assoziativen Zugriff und std::make_heap, std::push_heap und std::pop_heap Als Implementierung der Prioritätswarteschlange innerhalb des Vektors sind die Iteratoren in der Zuordnung nach Heap-Operationen nicht gültig.
• Wenn ich std::list (oder std::map) statt std::vector in der vorherige Konfiguration, std::make_heap etc. nicht becasue ihre Iteratoren kompiliert wird nicht aritmetic unterstützen.
• Wenn ich std::priority_queue verwenden möchte, kann ich die Artikelpriorität nicht aktualisieren.

Die Fragen sind:

• Fehle ich etwas offensichtlich, wie dieses Problem gelöst werden könnte?
• Können Sie mich auf eine reine C++/STL-Implementierung des LFU-Caches hinweisen, die den vorherigen Anforderungen als Beispiel entspricht?

Vielen Dank für Ihre Einblicke.

Answer 1

Ihre make-Implementierung mit den *_heap Funktionen und ein Vektor scheint eine gute Passform zu sein. obwohl es zu langsamen Updates führen wird. Das Problem der Iterator-Invalidation, das auftritt, ist normal für jeden Container, der einen Vektor als zugrunde liegende Datenstruktur verwendet. Dies ist der Ansatz, der auch von boost::heap::priority_queue unternommen wird, aber er stellt aus dem oben genannten Grund keine veränderbare Schnittstelle bereit. Andere boost::heap data-structures bieten die Möglichkeit, den Heap zu aktualisieren.

Etwas, das ein wenig seltsam scheint: Selbst wenn Sie std::priority_queue verwenden könnten, werden Sie immer noch das Iterator-Invalidierungsproblem haben.

Um Ihre Fragen direkt zu beantworten: Sie verpassen nicht etwas Offensichtliches. std::priority_queue ist nicht so nützlich wie es sein sollte. Der beste Ansatz besteht darin, eine eigene Heap-Implementierung zu schreiben, die Aktualisierungen unterstützt. Es ist ziemlich schwierig und nicht einfach, es vollständig STL-kompatibel zu machen (insbesondere Allokator-bewusst). Implementieren Sie außerdem den LFU-Cache.

Für den ersten Schritt, schauen Sie sich die Boost-Implementierungen an, um sich ein Bild von dem Aufwand zu machen. Mir ist keine Referenzimplementierung für den zweiten bekannt.

Um Iterator-Invalidierung zu umgehen, können Sie immer Indirection in einen anderen Container wählen, obwohl Sie versuchen sollten, es zu vermeiden, da es zusätzliche Kosten verursacht und ziemlich unordentlich werden kann.

Answer 2

Eine etwas einfachere Lösung als zwei Strukturen, um Daten zu halten:

• nur eine Karte halten, die Ihre Schlüssel zuordnet ihren Wert/use-count-Paar.
• , wenn der Cache voll ist:
• • einen Vektor von Iteratoren auf die Kartenelemente (O(n))
• • Verwendung schaffen std::nth_element die schlechteste 10% (O(n))
  zu finden
• • entfernen Sie sie alle aus der Karte (O(n log n))

Also, in den Cache ein neues Element hinzuzufügen, ist häufig Fall O(log n), worst case O(n log n) und abgeschrieben O(log n).

Das Entfernen der schlechtesten 10% könnte in einem LFU-Cache etwas drastisch sein, da neue Einträge die oberen 90% ausmachen müssen oder sie abgeschnitten werden. Wenn Sie nur ein Element entfernen, müssen neue Einträge immer noch vor dem nächsten neuen Eintrag aus dem unteren Bereich entfernt werden, oder sie werden abgeschnitten und haben dafür weniger Zeit. Also, je nachdem, warum LFU die richtige Caching-Strategie für Sie ist, könnte meine Umstellung darauf die falsche Strategie sein, oder es könnte immer noch in Ordnung sein.