29

LRU 手法を使用してキャッシュ置換を実装する必要がある C++ コードがいくつかあります。
これまでのところ、LRU キャッシュの置き換えを実装する 2 つの方法を知っています。

  1. キャッシュされたデータにアクセスするたびに timeStamp を使用し、最終的に置換時の timeStamp を比較します。
  2. キャッシュされたアイテムのスタックを使用し、それらが最近アクセスされた場合はそれらを一番上に移動するため、最終的に一番下に LRU 候補が含まれます。

では、製品コードで使用するのに適しているのはどれでしょうか?
彼らの他のより良い方法はありますか？

4

5 に答える 5

39

最近、ハッシュ マップ上に展開されたリンク リストを使用して、LRU キャッシュを実装しました。

    /// 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;

すべての重要な操作に対して O(1) であるという利点があります。

挿入アルゴリズム:

// 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--;
}
于 2010-01-13T14:50:47.700 に答える
11

これは、LRU キャッシュの非常に単純な実装です。

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

使い方は簡単で、その仕組みを理解することもできます。コードの合計サイズは約 50 行です。

于 2013-06-21T06:45:42.357 に答える
6

簡単にするために、Boost の MultiIndex マップの使用を検討する必要があるかもしれません。キーをデータから分離すると、同じデータで複数のキー セットがサポートされます。

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

「... 2 つのインデックスを使用します。1) キーで値を検索するためにハッシュされます 2) 最近使用された最後のアイテムを追跡するためにシーケンシャル (取得関数はアイテムをシーケンスの最後のアイテムとして配置します。キャッシュからいくつかのアイテムを削除する必要がある場合は、それらを削除する場合があります。シーケンスの最初から)」

「プロジェクト」演算子は、「プログラマーが同じ multi_index_container の異なるインデックス間を効率的に移動できるようにする」ことに注意してください。

于 2010-07-20T02:36:39.210 に答える
4

この記事では、STL コンテナーのペア (キーと値のマップとキー アクセス履歴のリスト)、または単一のboost::bimap.

于 2010-11-26T14:27:55.120 に答える
2

私たちの運用環境では、 Linux カーネルのリンク リストに似た C++ の二重リンク リストを使用しています。その優れた点は、必要な数のリンク リストにオブジェクトを追加できることと、リスト操作が高速かつシンプルであることです。

于 2010-01-13T17:49:02.977 に答える