オリジン
最近、学習アルゴリズムに関する小さなコースを買いました。
next.jsを使っていた頃、最適化のために訪問したページをキャッシュするためにLRUを使うという記事を読みました。
Redisも内部でLRUキャッシュ機構を使っていると聞いたことがあります。
その結果、学ぶべき情報を探したので、また忘れたときのためにここに記録しておきます。
LRUキャッシュ・メカニズムとは
LRU キャッシング・メカニズム、つまり最近使用されたデータの少ないキャッシング・ポリシーが使用されます。これは、あるデータが最近アクセスされていない場合、将来アクセスされる可能性も低いという原理に基づいています。つまり、限られたメモリ領域で他に利用できる領域がない場合、最も長い期間アクセスされていないデータは削除されるべきです。
下図をご覧ください：
3つの白いブロックは、先入れ先出しの法則に従う連鎖表と見なすことができ、この連鎖表に1、0、7を詰め込むと、7は最も長い未使用データとして排除されます。
0は一度しか使わないので、原則に従って下から頭へ移動させます。
leetcode146
データ構造の知識を使って、LRUキャッシング・メカニズムを設計し、実装してください。この機構は、次の操作をサポートする必要があります: データの取得とデータの書き込み。
データの取得 get(key) - キーの値がキャッシュに存在する場合はその値を取得し、存在しない場合は -1 を返します。 データの書き込み put(key, value) - キーのデータ値が既に存在する場合はその値を変更し、存在しない場合は "key/value" のセットを挿入します。キャッシュの容量が限界に達すると、新しいデータを書き込む際に、最も長い未使用のデータ値を削除して、新しいデータ値のためのスペースを確保する必要があります。
上級者向け。
両方の操作をO(1)の時間複雑度で実行できますか？
例
LRUCache cache = new LRUCache( 2 /* キャッシュサイズ*/ );
cache.put(1, 1);
cache.put(2, 2);
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
leetcode問題146の解答
トピックの要件は、O(1)の時間複雑さで両方の操作を完了することです。
MapとChained Listには2つのデータ構造があります。
Mapのキー値にアクセスする時間の複雑さはO(1)です。
連鎖テーブルへのノードの追加と削除の時間複雑度はO(1)
次の図は、マップと連鎖テーブルの関係を明確に表しています：
Java
class LRUCache {
private Map<Integer, LRUNode> cache = new HashMap<>();
private int count;
private int capacity;
private LRUNode head, tail;
public LRUCache(int capacity) {
this.count = 0;
this.capacity = capacity;
this.head = new LRUNode();
this.tail = new LRUNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
LRUNode node = cache.get(key);
if (node != null) {
// ノードが存在する、最近使用された、ノードをトップに置く
this.moveToHead(node);
return node.value;
}
return -1;
}
public void put(int key, int value) {
LRUNode node = cache.get(key);
if (node != null) {
// ノードが存在する、最近使用された、ノードをトップに置く
node.value = value;
this.moveToHead(node);
} else {
// ノードが存在しないので、新しいノードをトップに追加する
LRUNode newNode = new LRUNode(key, value);
this.cache.put(key, newNode);
this.addNode(newNode);
++this.count;
if (this.count > this.capacity) {
// 容量を超えたら一番下のノードを削除する
LRUNode tail = this.removeTail();
this.cache.remove(tail.key);
--this.count;
}
}
}
private void moveToHead(LRUNode node) {
this.removeNode(node);
this.addNode(node);
}
private void addNode(LRUNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(LRUNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private LRUNode removeTail() {
LRUNode res = tail.prev;
removeNode(res);
return res;
}
private class LRUNode {
int key;
int value;
LRUNode prev;
LRUNode next;
LRUNode() {}
LRUNode(int key, int value) {
this.key = key;
this.value = value;
}
}
}
JavaScript
/**
* @param {any} value
*/
var isNil = function(value) {
return value === null || value === undefined;
}
/**
* @param {number} key
* @param {number} value
*/
var LRUNode = function(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.size = 0;
this.capacity = capacity;
this.cache = new Map();
this.head = new LRUNode(null, null);
this.tail = new LRUNode(null, null);
this.head.next = this.tail;
this.tail.prev = this.head;
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
var node = this.cache.get(key);
if (!isNil(node)) {
this.moveToHead(node);
return node.value;
}
return -1;
};
/**
* @param {number} node
*/
LRUCache.prototype.moveToHead = function(node) {
this.removeNode(node);
this.addNode(node);
};
/**
* @param {number} node
*/
LRUCache.prototype.removeNode = function(node) {
var prevNode = node.prev;
var nextNode = node.next;
if (!isNil(nextNode))
prevNode.next = node.next;
if (!isNil(nextNode))
nextNode.prev = node.prev;
};
/**
* @param {number} node
*/
LRUCache.prototype.addNode = function(node) {
node.prev = this.head;
node.next = this.head.next;
this.head.next.prev = node;
this.head.next = node;
};
/**
* @param {number} node
*/
LRUCache.prototype.removeTail = function() {
var node = this.tail.prev;
this.removeNode(node);
return node;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
var node = this.cache.get(key);
if (!isNil(node)) {
node.value = value;
this.moveToHead(node);
} else {
var newNode = new LRUNode(key, value);
this.cache.set(key, newNode);
this.addNode(newNode);
this.size ++;
if (this.size > this.capacity) {
var tailNode = this.removeTail();
this.cache.delete(tailNode.key);
this.size --;
}
}
};
