LRU (Least Recently Used) キャッシュアルゴリズムの実装

[[349478]]

LRU は Least Recently Used の略で、よく使われるページ置換アルゴリズムです。長い間使われていないページを削除します。実は、これも非常にシンプルで、人気のないページを適時に削除して、トイレを占領してリソースを無駄にしないようにするものです。

LRU は一般的なページ置換アルゴリズムです。コンピューティングでは、すべてのファイル操作をメモリ内で実行する必要があります。ただし、コンピュータのメモリのサイズは固定されているため、すべてのファイルをメモリにロードすることはできません。そのため、メモリに追加されるファイルを選択する戦略を開発する必要があります。

一般的なページ置換アルゴリズムは次のとおりです。

LRU 最近未使用
FIFO先入先出置換アルゴリズムはキューに似ている
OPT 最適順列アルゴリズム (理想)
NRU クロック置換アルゴリズム
LFU 最も使用頻度の低い置換アルゴリズム
PBA ページバッファアルゴリズム

LRU原則

LRU の設計原則は、データが最近の期間に頻繁にアクセスされた場合、将来も頻繁にアクセスされるというものです。つまり、頻繁にアクセスされるデータであれば、すぐにヒットするようにする必要があり、頻繁にアクセスされないデータであれば、容量が制限を超えたときに削除する必要があります。

コアはスタックを使用して操作を実行することであり、主にgetとputの2つの操作が含まれます。

得る

取得時に、スタック内に値がある場合は、その値のキーがスタックの先頭に移動され、ない場合は null が返されます。

置く

スタックがいっぱいでないとき、スタックに入れるキーがあれば、そのキーに対応する値を更新し、キーの値をスタックの一番上に持ってきます。入れるキーがない場合は、そのままスタックにプッシュします。

スタックがいっぱいになったとき、スタックに入れるキーがある場合は、このキーに対応する値を更新し、キーの値をスタックの一番上に置きます。スタックに入れるキーがない場合は、スタックの一番下の要素を削除し、値をスタックの一番上に置きます。

解決策:配列を維持し、get メソッドと put メソッドを提供し、最大数を制限します。

get を使用すると、要素を最近使用したものとしてマークし、最初の項目に昇格させることができます。 put はキー値を追加できますが、最大制限に達したかどうかを判断する必要があります。

達していない場合は、配列の最初の項目に直接挿入できます。最大制限 max に達した場合は、データの末尾の要素を削除する必要があります。

 LRUCache cache = new LRUCache( 2 /* キャッシュ容量 */ ); 
 
キャッシュに1をセットします。
キャッシュにデータを格納する。
 cache.get(1); // 1を返す
cache.put(3, 3); // この操作によりキー2が無効になります
cache.get(2); // -1 を返します (見つかりません)
 cache.put(4, 4); // この操作によりキー1が無効になります
cache.get(1); // -1 を返します (見つかりません)
 cache.get(3); // 3 を返す
cache.get(4); // 4を返す

LRUアルゴリズムの設計

上記の操作プロセスを分析すると、putメソッドとgetメソッドの時間計算量をO(1)にするために、キャッシュデータ構造に必要な条件として、高速検索、高速挿入、高速削除、および順序をまとめることができます。

明らかに、キャッシュは最近使用されたデータと長い間使用されていないデータを区別するためにソートされる必要があるため、キーがすでに存在するかどうかを確認するためにキャッシュを調べる必要があり、容量がいっぱいの場合は最後のデータを削除する必要があり、各アクセスではデータをキューの先頭に挿入する必要もあります。

では、上記の条件を同時に満たすデータ構造は何でしょうか? ハッシュテーブルは検索が高速ですが、データには固定の順序がありません。リンクリストには順序があり、挿入と削除は高速ですが、検索は低速です。そこで、これらを組み合わせて、ハッシュリンクリストという新しいデータ構造を形成します。

LRU キャッシュアルゴリズムのコアデータ構造は、二重リンクリストとハッシュテーブルを組み合わせたハッシュリストです。このデータ構造は次のようになります。

js実装

特定のコードの一般的な解決策は、配列項目にキーと値のペアのオブジェクトを格納する配列を維持することです。毎回、キー値が配置されている配列インデックス操作を見つけるためにトラバースする必要があります。

leetCode 146 テストに合格しました。実行時間: 720 ミリ秒。メモリ使用量: 58.5 MB。

関数LRUCache(容量) {
    this.capacity = capacity; // 最大制限
    this.cache = [];
 }; 
 
 /**
 * @param {数値}キー 
 * @return {数値}
 */
 LRUCache.prototype.get =関数(キー) {
    index = this.cache.findIndex((item) => item.key === key )とします。
    if (インデックス=== -1 ) {
 -1 を返します。
    }
    // この要素を削除し、配列の最初の項目に挿入します
    値を this.cache[インデックス].value とします。
    this.cache.splice(インデックス, 1);
    this.cache.unshift({
鍵、
        価値、
    });
戻り値;
 }; 
 
 /**
 * @param {数値}キー 
 * @param {数値} 値
 * @return {void}
 */
 LRUCache.prototype.put =関数(キー、値) {
    index = this.cache.findIndex((item) => item.key === key )とします。
    // 挿入したいデータは既に存在するので、それを昇格するだけです
    if (インデックス> -1 ) {
        this.cache.splice(インデックス, 1);
    }そうでない場合 (this.cache.length >= this.capacity) {
        // 最大制限に達した場合は、最初に最も長い間使用されていないものを削除します
        this.cache.pop();
    }
    this.cache.unshift({キー、値 });
 };

実際には、上記のアプローチにはバリエーションがあります。オブジェクトを使用してキーと値のペアを保存し、配列を使用してキーの順序を保存できます。

高度な要件 O(1)

時間の計算量は O(1) なので、配列を走査してキー値を見つけることはできません。 ES6 の Map を使用するとこの問題を解決できます。Map はキーと値のペアを維持できるだけでなく、挿入順序も記憶できるためです。

関数LRUCache(容量) {
    this.cache = 新しい Map();
    this.capacity = capacity; // 最大制限
}; 
 
 LRUCache.prototype.get =関数(キー) {
    if (this.cache.has(キー)) {
        // 存在する場合は更新する
        temp = this.cache.get(キー) とします。
        this.cache.delete (キー) ;
        this.cache.set (キー、 temp ) ;
戻る 温度;
    }
 -1 を返します。
 }; 
 
 LRUCache.prototype.put =関数(キー、値) {
    if (this.cache.has(キー)) {
        // 存在する場合は更新します（削除してから追加します）
        this.cache.delete (キー) ;
    }そうでない場合 (this.cache.size > = this.capacity) {
        // 存在しない場合は追加します
        // キャッシュが最大値を超えた場合は、最近使用されていないものを削除します
        this.cache.delete (this.cache.keys(). next ().value);
    }
    this.cache.set (キー、値 );
 };