10

純粋な STL を使用して LFU (最も頻繁に使用されない) キャッシュを実装しようとしています (Boost は使用したくありません!)。

要件は次のとおりです。

  • Keylike withを使用した任意の要素への連想アクセスstd::map。
  • 最も優先度の低いアイテムを解放する能力 (そのUsesCount属性を使用)。
  • UsesCount任意の項目の優先度 ( ) を更新する機能。

問題は次のとおりです。

  • std::vector項目 ( Key、Value、UsesCount)std::mapのコンテナーとして、連想アクセス用のベクターへの反復子のコンテナーとしてstd::make_heap、std::push_heapおよびstd::pop_heapをベクター内の優先度キューの実装として使用すると、マップ内の反復子はヒープ操作後に無効になります。
  • 以前の構成の代わりにstd::list(または)を使用すると、反復子が算術をサポートしていないため、コンパイルできません。std::mapstd::vectorstd::make_heap
  • を使用したいのですがstd::priority_queue、アイテムの優先度を更新する機能がありません。

質問は次のとおりです。

  • この問題をどのように解決できるか明らかな何かが欠けていますか?
  • 例として、以前の要件を満たす LFU キャッシュの純粋な C++/STL 実装を教えてください。

あなたの洞察に感謝します。

4

2 に答える 2

3

関数とベクトルを使用した make の実装*_heapは適切なようです。ただし、更新は遅くなります。発生する反復子の無効化に関する問題は、ベクターを基礎となるデータ構造として使用するすべてのコンテナーにとって正常です。これはboost::heap::priority_queueでも採用されているアプローチですが、上記の理由により変更可能なインターフェースを提供していません。その他のboost::heap データ構造は、ヒープを更新する機能を提供します。

少し奇妙に思えること: 使用できたとしてstd::priority_queueも、イテレータの無効化の問題に直面することになります。

質問に直接答えるには: 明らかな何かが欠けているわけではありません。std::priority_queueあるべきほど有用ではありません。最良の方法は、更新をサポートする独自のヒープ実装を作成することです。完全な STL 互換 (特にアロケータ対応) にすることは、かなりトリッキーで単純な作業ではありません。その上で、LFU キャッシュを実装します。

最初のステップとして、Boost の実装を見て、取り組みの概要を把握してください。2番目の参照実装は知りません。

イテレータの無効化を回避するには、いつでも別のコンテナーへの間接化を選択できますが、追加のコストが発生し、非常に面倒になる可能性があるため、回避するようにしてください。

于 2012-07-10T08:51:59.323 に答える
1

2 つのデータ構造を保持するよりもやや単純なアプローチ:

  • キーを値/使用回数のペアにマップするマップを保持するだけです。
  • キャッシュがいっぱいの場合:
    • マップ要素への反復子のベクトルを作成します ( O(n))
    • std::nth_element最悪の 10% を見つけるために使用します ( O(n))
    • それらをすべてマップから削除します ( O(n log n))

したがって、新しい要素をキャッシュに追加することは、一般的なケースO(log n)、最悪のケースO(n log n)、および償却されO(log n)ます。

最悪の 10% を削除することは、LFU キャッシュでは少し劇的かもしれません。新しいエントリが上位 90% にならなければならないか、それらがカットされるからです。繰り返しになりますが、要素を 1 つだけ削除すると、新しいエントリは次の新しいエントリの前に底から降りる必要があります。そうしないと、カットされてしまい、そうする時間が少なくなります。したがって、LFU が適切なキャッシング戦略である理由によっては、LFU への変更が間違った戦略である場合もあれば、それでも問題ない場合もあります。

于 2012-07-10T09:33:55.607 に答える