C++ を使用して LRU キャッシュを実装しようとしています。それらを実装するのに最適な設計は何かを知りたいです。LRU が find() を提供し、要素を追加し、要素を削除する必要があることはわかっています。remove は LRU 要素を削除する必要があります。これを実装するのに最適な ADT は何ですか?例: 要素を値として、時間カウンターをキーとして使用するマップを使用すると、O(logn) 時間で検索できます。挿入は O(n)、削除は O(logn) です。
19783 次
7 に答える
15
LRU キャッシュの主な問題の 1 つは、"const" 操作がほとんどないことです。ほとんどの場合、基になる表現が変更されます (アクセスされた要素をぶつけるという理由だけで)。
これはもちろん、従来の STL コンテナではないことを意味するため、非常に不便です。したがって、イテレータを表示するという考えは非常に複雑です。イテレータが逆参照されると、これはアクセスであり、反復しているリストを変更する必要があります...オーマイ。
また、速度とメモリ消費の両方の観点から、パフォーマンスに関する考慮事項があります。
残念ながら、データをキュー (LRU) に整理する方法が必要になります (途中から要素を削除する可能性があります)。これは、要素が互いに独立している必要があることを意味します。もちろん、 Astd::listは適合しますが、必要以上です。ここでは片方向リストで十分です。リストを逆方向に繰り返す必要がないからです (結局のところ、キューが必要なだけです)。
ただし、これらの主な欠点の 1 つは、参照の局所性が低いことです。さらに速度が必要な場合は、ノードに独自のカスタム (プール ?) アロケータを提供して、それらができるだけ近くに保たれるようにする必要があります。これにより、ヒープの断片化も多少緩和されます。
次に、明らかにインデックス構造が必要です (キャッシュ ビット用)。最も自然なのは、ハッシュ マップに向かうことです。std::tr1::unordered_map、std::unordered_mapまたはboost::unordered_map通常は高品質の実装です。いくつかは利用できるはずです。また、ハッシュ衝突処理用に追加のノードを割り当てます。他の種類のハッシュ マップを好むかもしれません。この件に関するウィキペディアの記事をチェックし、さまざまな実装技術の特徴について読んでください。
続いて、(明らかな) スレッドのサポートがあります。スレッドのサポートが必要ない場合は問題ありませんが、必要な場合は少し複雑になります。
- 前述
constしたように、このような構造に対する操作はほとんどないため、読み取り/書き込みアクセスを区別する必要はありません。 - 内部ロックは問題ありませんが、用途によってはうまくいかない場合があります。内部ロックの問題は、呼び出しごとにロックを放棄するため、「トランザクション」の概念をサポートしていないことです。この場合は、オブジェクトをミューテックスに変換し、
std::unique_ptr<Lock> lock()メソッドを提供します (デバッグでは、各メソッドのエントリ ポイントでロックが取得されるよりもアサートできます)。 - (ロック戦略では) 再入の問題があります。つまり、同じスレッド内からミューテックスを「再ロック」する機能です。利用可能なさまざまなロックとミューテックスの詳細については、Boost.Thread を確認してください。
最後に、エラー報告の問題があります。入力したデータをキャッシュで取得できない可能性があることが予想されるため、例外「悪趣味」の使用を検討します。ポインター ( Value*) またはBoost.Optional ( ) のいずれかを検討してくださいboost::optional<Value&>。セマンティックが明確であるため、Boost.Optional を好みます。
于 2010-09-04T16:02:24.760 に答える
7
LRUを実装する最良の方法は、std::listとstdext::hash_mapの組み合わせを使用することです（std、std :: mapのみを使用したい）。
- 最後に最後に使用されたものが最も少なくなるようにデータをリストに格納し、マップを使用してリストアイテムをポイントします。
- 「get」の場合は、マップを使用してリストaddrを取得し、データを取得して、現在のノードを
最初のノードに移動し（これが現在使用されているため）、マップを更新します。 - 「挿入」の場合、リストから最後の要素を削除し、新しいデータを前面に追加して、マップを更新します。
これは、取得できる最速です。hash_mapを使用している場合は、ほとんどすべての操作をO（1）で実行する必要があります。std :: mapを使用する場合は、すべての場合にO（logn）を取る必要があります。
非常に優れた実装がここにあります
于 2010-09-04T00:22:47.190 に答える
5
この記事では、いくつかの C++ LRU キャッシュの実装 (STL を使用するものと を使用するものboost::bimap) について説明します。
于 2010-12-15T13:22:45.113 に答える
2
優先度と言えば当然にincrease-keyやdelete-minにつながる「ヒープ」だと思います。
于 2010-09-03T21:47:57.883 に答える
2
キャッシュを避けることができれば、キャッシュを外の世界から見えるようにすることはまったくありません。コレクション (何でも) を用意し、必要に応じてアイテムを追加および削除して、キャッシュを目に見えないように処理しますが、外部インターフェイスは、基になるコレクションのものとまったく同じです。
実装に関する限り、ヒープはおそらく最も明白です。マップとほぼ同様の複雑さがありますが、リンクされたノードからツリーを構築する代わりに、アイテムを配列に配置し、「リンク」は配列インデックスに基づいて暗黙的です。これにより、キャッシュのストレージ密度が向上し、「実際の」(物理) プロセッサ キャッシュの局所性が向上します。
于 2010-09-03T21:52:12.137 に答える
0
C++ では通常のヒープを使用します。
std::make_heap (標準では O(n) であることが保証されています)、std::pop_heap、および #include の std::push_heap を使用すると、それを実装するのは非常に簡単です。増加キーについてのみ心配する必要があります。
于 2010-09-03T22:06:19.793 に答える
0
ヒープと、おそらくフィボナッチ ヒープをお勧めします
于 2010-09-03T21:47:51.427 に答える