LRUとは何か、JavaScriptでLRUキャッシュメカニズムを実装する方法
- 969単語
- 5分
- 08 Aug, 2024
はじめに
LRU は Least Recently Used の略で、キャッシュ置換戦略の一つです。キャッシュがそのストレージ上限に達したとき、LRUは最も長い間使用されていないエントリを削除します。この戦略は、最近使用されたデータは将来も使用される可能性が高く、長い間使用されていないデータは再び使用される可能性が低いと仮定しています。
LRUキャッシュのJavaScript実装
JavaScriptでLRUキャッシュを実装するには、Map
と双方向リスト
を使用することができます。Map
は要素の挿入順序を保証し、双方向リストは最近使用された要素をリストの先頭に移動させ、最も長い間使用されていない要素を効率的に削除するのに役立ちます。
コード実装
以下は簡単なLRUキャッシュの実装です:
1// 双方向リストのノードクラスを定義2class Node {3 constructor(key, value) {4 this.key = key;5 this.value = value;6 this.prev = null;7 this.next = null;8 }9}10
11// LRUキャッシュクラスを定義12class LRUCache {13 constructor(capacity) {14 this.capacity = capacity; // キャッシュ容量15 this.map = new Map(); // キャッシュデータを保存16 this.head = new Node(null, null); // 仮想ヘッドノード17 this.tail = new Node(null, null); // 仮想テールノード18 this.head.next = this.tail;19 this.tail.prev = this.head;20 }21
22 // キャッシュ値を取得23 get(key) {24 if (!this.map.has(key)) {25 return -1; // キャッシュにキーがない場合は-1を返す26 }27
28 const node = this.map.get(key);29 this._remove(node); // 双方向リストからノードを削除30 this._add(node); // ノードをリストの末尾に追加(最近使用)31
32 return node.value;33 }34
35 // キャッシュ値を追加または更新36 put(key, value) {37 if (this.map.has(key)) {38 this._remove(this.map.get(key)); // キャッシュに既にキーがある場合、古いノードを削除39 }40
41 const newNode = new Node(key, value);42 this._add(newNode); // 新しいノードをリストの末尾に追加43 this.map.set(key, newNode);44
45 if (this.map.size > this.capacity) {46 const lruNode = this.head.next; // 最も長い間使用されていないノードを取得47 this._remove(lruNode); // リストから最も長い間使用されていないノードを削除48 this.map.delete(lruNode.key); // キャッシュから最も長い間使用されていないキーを削除49 }50 }51
52 // 双方向リストからノードを削除53 _remove(node) {54 node.prev.next = node.next;55 node.next.prev = node.prev;56 }57
58 // ノードを双方向リストの末尾に追加59 _add(node) {60 node.prev = this.tail.prev;61 node.next = this.tail;62 this.tail.prev.next = node;63 this.tail.prev = node;64 }65}
使用例
1const lru = new LRUCache(2);2
3lru.put(1, 1);4lru.put(2, 2);5console.log(lru.get(1)); // 出力 16lru.put(3, 3); // キー2を削除7console.log(lru.get(2)); // 出力 -1 (見つからない)8lru.put(4, 4); // キー1を削除9console.log(lru.get(1)); // 出力 -1 (見つからない)10console.log(lru.get(3)); // 出力 311console.log(lru.get(4)); // 出力 4
コード解説
- Node クラス:双方向リストのノードを表し、
key
とvalue
、およびprev
とnext
ポインタを含みます。 - LRUCache クラス:キャッシュを管理する主要なクラスで、初期化時に容量
capacity
を設定し、Map
と二つの番兵ノードhead
とtail
を作成します。 - get メソッド:キャッシュから値を取得し、存在する場合はノードを末尾に移動します(最近使用)。
- put メソッド:新しい値をキャッシュに挿入し、キャッシュに既にそのキーが存在する場合は古いノードを削除します。新しいノードを挿入後、容量を超えている場合は先頭のノード(最も長い間使用されていない)を削除します。
- _remove メソッド:双方向リストからノードを削除します。
- _add メソッド:ノードを双方向リストの末尾に追加します。
この実装により、get
と put
操作が定数時間 ( O(1) ) で実行できることが保証されます。
まとめ
上記のコードと詳細なコメントを通じて、JavaScriptを使用して簡単なLRUキャッシュを実装する方法を理解しました。LRUキャッシュは一般的なキャッシュ置換戦略であり、さまざまなキャッシュシステムで広く使用されています。この記事がLRUキャッシュの実装原理と応用について理解を深める一助となれば幸いです。