origin
Recently, I bought a small class to learn algorithms, which is very good, and it mentions the LRU caching mechanism.
Actually, this isn’t the first time I’ve heard of LRU. When I was working with Nex.js, I read an article about using an LRU cache to optimize the pages I visited.
I heard that Redis also uses LRU caching mechanism.
Therefore, I found some materials to study, in order to avoid forgetting again, here is a record.
What is the LRU caching mechanism
LRU caching mechanism, which uses the least recently used caching strategy. The principle is that if a piece of data has not been accessed recently, there is a small chance that it will be accessed in the future. This means that the data that has not been accessed for the longest time should be removed when there is no more space available in the limited memory space.
Here’s how it works:
The three white blocks can be thought of as a linked list. The list follows a first-in, first-out rule. When the list is filled with 1,0,7, 7 is eliminated as the longest unused data.
0 is used once, so follow the rule and move it from the bottom to the head.
Leetcode146 topic
Using your data structures, design and implement an LRU (least recently used) caching mechanism. It should support the following operations: getting data get and writing data PUT.
Get (key) – Gets the value of the key (always positive) if it exists in the cache, otherwise returns -1. Write data put(key, value) – If the keyword already exists, change its data value; If the keyword does not exist, the keyword/Value group is inserted. When the cache reaches its maximum capacity, it should delete the longest unused data values before writing new data to make room for new data values.
Advanced:
Can you do both in order one time?
Example:
LRUCache cache = new LRUCache(2 /* cache size */); cache.put(1, 1); cache.put(2, 2); cache.get(1); // Return 1 cache.put(3, 3); // This operation invalidates keyword 2 cache.get(2); // Return -1 (not found) cache.put(4, 4); // This operation invalidates keyword 1 cache.get(1); // Return -1 (not found) cache.get(3); // Return 3 cache.get(4); / / return 4Copy the codeSolution to leetcode146
And the question is to do both of these in order of one time.
Two data structures can be thought of: Map and linked lists.
The time complexity of Map access key value is O(1)
It takes O(1) time to add and remove nodes from the list.
The following diagram clearly reflects the relationship between Map and linked list:
My answer key
Java version
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) {
// The node exists, recently used, put the node at the top
this.moveToHead(node);
return node.value;
}
return -1;
}
public void put(int key, int value) {
LRUNode node = cache.get(key);
if(node ! =null) {
// The node exists, recently used, put the node at the top
node.value = value;
this.moveToHead(node);
} else {
// If the node does not exist, add a node to the top
LRUNode newNode = new LRUNode(key, value);
this.cache.put(key, newNode);
this.addNode(newNode);
++this.count;
if (this.count > this.capacity) {
// If the capacity exceeds the capacity, delete the bottom node
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(a) {
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; }}}Copy the codeThe JavaScript version
/ * * *@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(a);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 --; }}};Copy the codereference
- LeetCode leetcode-cn.com/problems/lr…