caching - LRUとLFUの違いは何ですか

Question

LRUとLFUキャッシュの実装の違いは何ですか?

を使用して LRU を実装できることを知っていLinkedHashMapます。しかし、LFU キャッシュを実装する方法は?

Answer 1

キャッシュ容量が 3 のキャッシュ要求の一定のストリームを考えてみましょう。以下を参照してください。

A, B, C, A, A, A, A, A, A, A, A, A, A, A, B, C, D

O(1) エビクション時間と O(1) ロード時間の HashMap + 二重リンク リストの実装を使用して、最近使用されていない (LRU)キャッシュを考えると、上記のようにキャッシュ リクエストを処理している間、次の要素がキャッシュされます。 .

[A]
[A, B]
[A, B, C]
[B, C, A] <- a stream of As keeps A at the head of the list.
[C, A, B]
[A, B, C]
[B, C, D] <- here, we evict A, we can do better! 

この例を見ると、もっとうまくやれることが簡単にわかります。将来的に A を要求する可能性が高くなると予想されるため、最近使用されていないものであっても削除すべきではありません。

A - 12
B - 2
C - 2
D - 1

使用頻度の低い (LFU)キャッシュは、キャッシュ リクエストが削除アルゴリズムで使用された回数を追跡することで、この情報を利用します。

Answer 2

LRU は、最長未使用キャッシュと呼ばれるキャッシュ削除アルゴリズムです。

このリソースを見てください

LFU は、最も使用頻度の低いキャッシュ と呼ばれるキャッシュ エビクション アルゴリズムです。

3 つのデータ構造が必要です。1 つはキー/値をキャッシュするために使用されるハッシュ テーブルで、キーを指定すると O(1) でキャッシュ エントリを取得できます。2 つ目は、アクセス頻度ごとの二重リンク リストです。ますます多くの頻度リスト エントリが作成されないように、最大​​頻度はキャッシュ サイズに制限されます。最大サイズ 4 のキャッシュがある場合、最終的に 4 つの異なる周波数になります。各頻度には、その特定の頻度に属するキャッシュ エントリを追跡するための二重リンク リストがあります。3 番目のデータ構造は、これらの周波数リストを何らかの方法でリンクすることです。配列または別のリンクされたリストのいずれかにすることができるため、キャッシュエントリにアクセスすると、時間 O(1) で次の頻度リストに簡単に昇格できます。

Answer 3

主な違いは、LRU では、最近使用されたページが他のページよりも古いページのみをチェックすることです。つまり、最近使用されたページのみに基づいてチェックします。しかし、LFUでは古いページとそのページの頻度をチェックし、ページの頻度が古いページよりも大きい場合はそれを削除できず、すべての古いページの頻度が同じ場合は最後に、つまりFIFOメソッドを使用します. ページを削除します....

Answer 4

• 一定時間の挿入は、LRU に対してのみ機能します。LFU を使用すると、少なくとも一定時間のルックアップを維持できます。何もないよりはましです。

• LFU では、動的に変化する優先順位に基づいてエントリの順序を維持するための最良の方法は、もちろん優先キューです。ヒープ、フィボナッチ ヒープ、またはその他の実装である可能性があります。ユーザーは、使用するプログラミング言語と、もちろん、使用するコンテキストに応じて、どの実装が最適かを考えるタスクに基づいて実装を選択できます。彼らはキャッシュを使用します。

• LRU から LFU に切り替えるためにキャッシングの実装を変更する必要があるのは 2 つだけです。

  1- エビクション ポリシー (削除する要素の選択に関するすべてのロジック)

  2-要素を格納するために使用されるデータ構造

• LFU キャッシュを作成するには、ハッシュマップと Treap を使用します。Treap は、バイナリ ツリーとプライオリティ キューの組み合わせです。treap のアイデアには、2 つの制約があり、そのうちの 1 つをバイナリ ツリーで構成し、もう 1 つを優先キューで構成します。このグラフを見てください：

hashmap の値は、treap ノードを指しています。トラップ ノードでは、小さな青い四角形の数字がアクセス数で、これがトラップの優先キュー部分です。子ノードは常に親ノードより優先度が高いことに注意してください。ただし、兄弟ノード間に順序付けはありません。

• LFU キャッシュが長時間実行されると、人気がなくなった古いエントリのターンアラウンド タイムが非常に長くなる可能性があります。

パフォーマンスの比較は次のとおりです。