LRU Umsetzung in der Produktion Code

Question

Ich habe einige C ++ Code, wo ich brauche Cache-Replacement mit LRU-Technik zu implementieren.
Bisher weiß ich zwei Methoden LRU-Cache-Ersatz zu implementieren:

1. Verwenden von Zeitstempel für jedes Mal, wenn die im Cache gespeicherten Daten zugegriffen wird, und schließlich die Zeitstempel zum Zeitpunkt des Ersatzes zu vergleichen.
2. einen Stapel von zwischengespeicherten Elemente verwenden und sie an die Spitze zu bewegen, wenn sie vor kurzem zugegriffen werden, so schließlich der Boden des LRU Candidate enthält.

Also, wer von ihnen ist besser in Produktionscode verwendet werden?
Gibt es irgendwelche anderen bessere Methoden?

Answer 1

Vor kurzem implementiert ich einen LRU-Cache eine verknüpfte Liste, verteilt auf einer Hash-Karte.

    /// Typedef for URL/Entry pair
    typedef std::pair< std::string, Entry > EntryPair;

    /// Typedef for Cache list
    typedef std::list< EntryPair > CacheList;

    /// Typedef for URL-indexed map into the CacheList
    typedef boost::unordered_map< std::string, CacheList::iterator > CacheMap;

    /// Cache LRU list
    CacheList mCacheList;

    /// Cache map into the list
    CacheMap mCacheMap;

Es hat den Vorteil, dass O (1) Für alle wichtigen Operationen.

Die Einfügung Algorithmus:

// create new entry
Entry iEntry( ... );

// push it to the front;
mCacheList.push_front( std::make_pair( aURL, iEntry ) );

// add it to the cache map
mCacheMap[ aURL ] = mCacheList.begin();

// increase count of entries
mEntries++;

// check if it's time to remove the last element
if ( mEntries > mMaxEntries )
{
    // erease from the map the last cache list element
    mCacheMap.erase( mCacheList.back().first );

    // erase it from the list
    mCacheList.pop_back();

    // decrease count
    mEntries--;
}

Answer 2

Hier ist eine sehr einfache Implementierung von LRU-Cache

https://github.com/lamerman/cpp-lru-cache .

Es ist einfach zu bedienen und zu verstehen, wie es funktioniert. Die Gesamtgröße des Code ist etwa 50 Zeilen.

Answer 3

Der Einfachheit halber, vielleicht sollten Sie prüfen, Multiindex-Karte mit boost. Wenn wir den Schlüssel aus dem Daten trennen, unterstützen wir mehrere Sätze von Tasten auf den gleichen Daten.

Von [ http://old.nabble.com/realization-of-Last-Recently-Used-cache-with-boost%3A%3Amulti_index-td22326432.html ]:

“... Verwendung zwei Indizes: 1) gehasht für Wert der Suche nach Schlüssel 2) sequenziellen für die Verfolgung zuletzt kürzlich verwendete Elemente (Funktion einstellen Artikel als letzten Punkt in sequesnce bekommen Wenn wir einige Elemente aus dem Cache entfernen, müssen wir. können sie löschen von Beginn der Sequenz). "

Beachten Sie, dass das „Projekt“ Operator „ermöglicht es dem Programmierer zwischen verschiedenen Indizes der gleichen multi_index_container zu bewegen“ effizient.

Answer 4

Die Artikel Implementierung beschreibt ein Paar von STL-Containern mit (einer Schlüssel-Wert-Karte sowie eine Liste für den Schlüssel Zugriffshistorie) oder eine einzelne boost::bimap.

Answer 5

In der Produktionsumgebung verwenden wir eine C ++ Doppel Liste verknüpft, die auf die Linux-Kernel-Liste verknüpft. Das Schöne daran ist, dass Sie ein Objekt so viele verknüpfte Listen hinzufügen können, wie Sie möchten und Listenoperation ist schnell und einfach.