誇張ではなく、絶対にそうはならない

01. はじめに

データのクエリ速度を向上させるために、キャッシュがよく使用されます。キャッシュ容量には制限があるため、キャッシュ容量が上限に達すると、新しいデータを追加できるように、一部のデータを削除してスペースを確保する必要があります。キャッシュされたデータはランダムに削除することはできません。一般的に、特定のアルゴリズムに基づいてキャッシュされたデータを削除する必要があります。一般的な除去アルゴリズムには、LRU、LFU、FIFO などがあります。この記事では、LRU アルゴリズムについて説明します。

02. LRUの紹介

LRU は Least Recently Used の略です。このアルゴリズムでは、最も最近使用されたデータはホットデータであり、次回も高い確率で再び使用されるとみなされます。最近ほとんど使用されていないデータは、次回も使用されなくなる可能性があります。キャッシュ容量がいっぱいになると、最近あまり使用されていないデータが最初に削除されます。

キャッシュの内部データが以下のようになっていると仮定します。

ここでは、リストの最初のノードをヘッドノード、最後のノードをテールノードと呼びます。

キャッシュを呼び出してキー = 1 のデータを取得する場合、図に示すように、LRU アルゴリズムはノード 1 をヘッドノードに移動する必要があり、他のノードは変更されません。

次にkey=8のノードを挿入します。このときキャッシュ容量が上限に達しているため、追加する前にデータを削除する必要があります。各クエリはデータをヘッドノードに移動するため、クエリされていないデータはテールノードに移動します。テールのデータは最もアクセスが少ないデータであると考えられるため、テールノードのデータは削除されます。

次に、データをヘッドノードに直接追加します。

LRU アルゴリズムの具体的な手順の概要は次のとおりです。

新しいデータはリストの先頭に直接挿入されます
キャッシュデータがヒットし、データがリストの先頭に移動される
キャッシュがいっぱいになったら、リストの末尾にあるデータを削除します。

03. LRUアルゴリズムの実装

上記の例からわかるように、LRU アルゴリズムではヘッドノードを追加し、テールノードを削除する必要があります。リンクリスト内のノードの追加/削除の時間計算量は O(1) であるため、ストレージキャッシュデータコンテナーとして非常に適しています。ただし、通常の一方向リンクリストは使用できません。一方向リンクリストには、いくつかの欠点があります。

任意のノードからデータを取得するたびに、最初のノードからトラバースする必要があり、その結果、ノードを取得する複雑さは O(N) になります。
中間ノードをヘッドノードに移動するには、中間ノードの前のノードの情報を知る必要があるため、一方向リンクリストを再度走査して情報を取得する必要があります。

上記の問題は、他のデータ構造を組み合わせることで解決できます。

ハッシュテーブルを使用してノードを格納すると、ノードを取得する複雑さは O(1) に削減されます。ノード移動の問題は、前のノード情報を記録するための先行ポインタをノードに追加することで解決できます。これにより、リンクリストが一方向リンクリストから双方向リンクリストに変更されます。

要約すると、図に二重リンクリストとハッシュテーブルの組み合わせを使用したデータ構造が示されています。

2 つの「センチネル」ノードは双方向リンクリストに意図的に追加されており、データの保存には使用されません。センチネルノードを使用すると、ノードを追加/削除するときに境界ノードが存在しないかどうかを考慮する必要がなくなり、プログラミングの難易度が軽減され、コードの複雑さが軽減されます。

LRU アルゴリズムの実装コードは次のとおりです。簡略化のため、key と val は両方とも int 型とみなされます。

パブリッククラスLRUCache { 
 
 エントリーヘッド、テール;
 int容量;
整数 サイズ;
 マップキャッシュ; 
 
 
パブリックLRUCache( int容量) {
 this.capacity = 容量;
 // リンクリストを初期化する
 リンクリストを初期化します。
サイズ= 0;
 キャッシュ = 新しい HashMap<>(容量 + 2);
 } 
 
 /**
 * ノードが存在しない場合は -1 を返します。存在する場合は、ノードをヘッド ノードに移動し、ノードのデータを返します。
 *
 * @paramキー 
 * @戻る 
 */
公共  int get( int  鍵） {
 エントリノード = cache.get( key );
 if (ノード == null ) {
 -1 を返します。
 }
 // モバイルノードがあります
 ノードを先頭に移動します。
ノード値を返します。
 } 
 
 /**
 * ヘッドノードにノードを追加します。容量がいっぱいになると、テールノードは削除されます。
 *
 * @paramキー 
 * @パラメータ値
 */
パブリックvoid put( int  キー、 int値）{
 エントリノード = cache.get( key );
 if (ノード != null ) {
 ノードの値 = 値;
 ノードを先頭に移動します。
戻る;
 }
 // 存在しません。最初に追加し、その後末尾のノードを削除します
 // この時点で容量がいっぱいなので、末尾のノードを削除します
 if (サイズ== 容量 ) {
 エントリ lastNode = tail.pre;
 最後のノードを削除します。
 cache.remove( lastNode.key );
サイズ- ;  
 }
 // ヘッドノードを追加する
 
 エントリ newNode = new Entry();
 newNode.key =キー;
 新しいノードの値 = 値;
 ノードを追加します(新しいノード)。
 cache.put(キー、newNode);
サイズ++; 
 
 } 
 
 プライベート void moveToHead(エントリノード) {
 // まず元のノードの関係を削除します
 ノードを削除します。
 ノードを追加します。
 } 
 
 プライベート void addNode(エントリノード) {
 ノードを次のノードにドラッグします。
 ノードの次=ヘッドの次; 
 
 ノードの先頭に、
 ノードを次に示します。
 } 
 
 プライベート void deleteNode(エントリノード) {
 ノードのpre.next =ノードのnext ;
 ノードを次のノードにリンクします。
 } 
 
 
公共 静的クラスエントリ{
公開エントリー事前;
公開エントリ次へ;
公共 整数 鍵;
公共  int値; 
 
パブリックエントリ( int  キー、 int値）{
 this.key =キー;
 this.value = 値;
 } 
 
パブリックエントリ() {
 }
 } 
 
 プライベートvoid initLinkedList() {
 head = 新しいエントリ();
 tail = 新しいエントリ(); 
 
 ヘッドの次= テール;
 tail.pre = ヘッド; 
 
 } 
 
公共 静的void main(String[] args) { 
 
 LRUCache キャッシュ = 新しい LRUCache(2); 
 
 キャッシュに1をセットします。
 キャッシュにデータを格納する。
 System.out.println (cache.get(1)) ;
 キャッシュにデータを格納する。
 System.out.println (cache.get(2)) ; 
 
 }
 }