LRUとは何か、JavaScriptでLRUキャッシュメカニズムを実装する方法

はじめに

LRULeast Recently Used の略で、キャッシュ置換戦略の一つです。キャッシュがそのストレージ上限に達したとき、LRUは最も長い間使用されていないエントリを削除します。この戦略は、最近使用されたデータは将来も使用される可能性が高く、長い間使用されていないデータは再び使用される可能性が低いと仮定しています。

LRUキャッシュのJavaScript実装

JavaScriptでLRUキャッシュを実装するには、Map双方向リストを使用することができます。Mapは要素の挿入順序を保証し、双方向リストは最近使用された要素をリストの先頭に移動させ、最も長い間使用されていない要素を効率的に削除するのに役立ちます。

コード実装

以下は簡単なLRUキャッシュの実装です:

1
// 双方向リストのノードクラスを定義
2
class 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キャッシュクラスを定義
12
class 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
}

使用例

1
const lru = new LRUCache(2);
2
3
lru.put(1, 1);
4
lru.put(2, 2);
5
console.log(lru.get(1)); // 出力 1
6
lru.put(3, 3); // キー2を削除
7
console.log(lru.get(2)); // 出力 -1 (見つからない)
8
lru.put(4, 4); // キー1を削除
9
console.log(lru.get(1)); // 出力 -1 (見つからない)
10
console.log(lru.get(3)); // 出力 3
11
console.log(lru.get(4)); // 出力 4

コード解説

  1. Node クラス:双方向リストのノードを表し、keyvalue、および prevnext ポインタを含みます。
  2. LRUCache クラス:キャッシュを管理する主要なクラスで、初期化時に容量 capacity を設定し、Map と二つの番兵ノード headtail を作成します。
  3. get メソッド:キャッシュから値を取得し、存在する場合はノードを末尾に移動します(最近使用)。
  4. put メソッド:新しい値をキャッシュに挿入し、キャッシュに既にそのキーが存在する場合は古いノードを削除します。新しいノードを挿入後、容量を超えている場合は先頭のノード(最も長い間使用されていない)を削除します。
  5. _remove メソッド:双方向リストからノードを削除します。
  6. _add メソッド:ノードを双方向リストの末尾に追加します。

この実装により、getput 操作が定数時間 ( O(1) ) で実行できることが保証されます。

まとめ

上記のコードと詳細なコメントを通じて、JavaScriptを使用して簡単なLRUキャッシュを実装する方法を理解しました。LRUキャッシュは一般的なキャッシュ置換戦略であり、さまざまなキャッシュシステムで広く使用されています。この記事がLRUキャッシュの実装原理と応用について理解を深める一助となれば幸いです。