82

最も使用頻度の低い (LRU) キャッシュは、使用頻度の最も低いアイテムを最初に破棄するものです。このようなキャッシュ クラスをどのように設計して実装しますか? 設計要件は次のとおりです。

1) できるだけ早くアイテムを見つける

2) キャッシュ ミスが発生してキャッシュがいっぱいになると、使用頻度の最も低いアイテムをできるだけ早く置き換える必要があります。

設計パターンとアルゴリズム設計の観点から、この問題をどのように分析して実装しますか?

4

14 に答える 14

108

リンク リスト + リンク リスト ノードへのポインターのハッシュ テーブルは、LRU キャッシュを実装する通常の方法です。これにより、O（1）操作が可能になります（適切なハッシュを想定）。これの利点 (O(1) であること): 構造全体をロックするだけで、マルチスレッド バージョンを実行できます。粒状ロックなどについて心配する必要はありません。

簡単に言えば、その仕組みは次のとおりです。

値にアクセスすると、リンクされたリスト内の対応するノードを先頭に移動します。

キャッシュから値を削除する必要がある場合は、末尾から削除します。

値をキャッシュに追加するときは、それをリンク リストの先頭に配置するだけです。

doublep のおかげで、C++ 実装のサイトがあります: Miscellaneous Container Templates。

于 2010-03-23T23:14:23.670 に答える
30

これは、ハッシュ (unordered_map) とリストの組み合わせを使用した、LRU キャッシュの単純な C++ 実装のサンプルです。リスト上のアイテムにはマップにアクセスするためのキーがあり、マップ上のアイテムにはリストにアクセスするためのリストのイテレータがあります。 

#include <list>
#include <unordered_map>
#include <assert.h>

using namespace std;

template <class KEY_T, class VAL_T> class LRUCache{
private:
        list< pair<KEY_T,VAL_T> > item_list;
        unordered_map<KEY_T, decltype(item_list.begin()) > item_map;
        size_t cache_size;
private:
        void clean(void){
                while(item_map.size()>cache_size){
                        auto last_it = item_list.end(); last_it --;
                        item_map.erase(last_it->first);
                        item_list.pop_back();
                }
        };
public:
        LRUCache(int cache_size_):cache_size(cache_size_){
                ;
        };

        void put(const KEY_T &key, const VAL_T &val){
                auto it = item_map.find(key);
                if(it != item_map.end()){
                        item_list.erase(it->second);
                        item_map.erase(it);
                }
                item_list.push_front(make_pair(key,val));
                item_map.insert(make_pair(key, item_list.begin()));
                clean();
        };
        bool exist(const KEY_T &key){
                return (item_map.count(key)>0);
        };
        VAL_T get(const KEY_T &key){
                assert(exist(key));
                auto it = item_map.find(key);
                item_list.splice(item_list.begin(), item_list, it->second);
                return it->second->second;
        };

};
于 2013-01-24T14:20:23.113 に答える
1

ここに LRU 実装があります。インターフェイスは std::map に準拠しているため、それほど使いにくいものではありません。さらに、データがキャッシュで無効化された場合に使用されるカスタム バックアップ ハンドラーを提供できます。

sweet::Cache<std::string,std::vector<int>, 48> c1;
c1.insert("key1", std::vector<int>());
c1.insert("key2", std::vector<int>());
assert(c1.contains("key1"));
于 2014-06-06T10:37:20.320 に答える
0

キャッシュはハッシュテーブルのようにキーによる値の取得をサポートするデータ構造ですか? LRU は、キャッシュに特定のサイズ制限があることを意味し、使用頻度の低いエントリを定期的に削除する必要があります。

リンクされたリスト + ポインターのハッシュテーブルを実装する場合、キーによる値の O(1) 取得をどのように行うことができますか?

各エントリの値が値+前/次のエントリへのポインタであるハッシュテーブルを使用してLRUキャッシュを実装します。

マルチスレッド アクセスに関しては、リーダー/ライター ロック (競合は通常高速であるため、理想的にはスピン ロックによって実装されます) を監視することをお勧めします。

于 2010-11-05T23:51:27.843 に答える