This is the seventh day of my participation in the First Challenge 2022. For details: First Challenge 2022.
The target
Design and implement a data structure that satisfies the LRU (least recently used) cache constraints. Implement the LRUCache class: Capacity Initializes the LRU cache int GET (int key) Returns the value of the key if the key exists in the cache; otherwise -1 is returned. Void put(int key, int value) If the key already exists, change its value. If not, the group key-value is inserted into the cache. If the number of keywords exceeds capacity due to an insert operation, you need to export the unused keywords. The functions get and PUT must run in O(1) average time complexity.
What is the LRU
LRU stands for Least Recently Used. It is a common page replacement algorithm that selects the pages that have not been Used for the most recent time to eliminate the page. The algorithm assigns each page an access field, which is used to record the time T experienced by a page since it was visited last time. When a page needs to be eliminated, the page with the largest T value in the existing page, that is, the least recently used page, is selected to be eliminated.
Introduction to the
The least Recently used algorithm (LRU) is a page replacement algorithm widely used by most operating systems to maximize page hit ratio. The idea of the algorithm is to replace the page that has not been used for the longest time when the page missing interruption occurs. From the principle of program operation, the least recently used algorithm is close to an ideal page replacement algorithm, which not only makes full use of the history information of page call in memory, but also correctly reflects the local problems of the program. The results of page replacement for the above example by LRU algorithm are shown in Figure 1. When the process accesses page 2 for the first time, it replaces page 7 because it is the most recent and unaccessed. When the process first accesses page 3, page 1 becomes the most recent and unused page, swap it out. It can be seen from Figure 1 that the images of the first 5 times are the same as those of the optimal displacement algorithm, but this is not an inevitable result. Because, the best substitution algorithm is from a “backward looking” point of view, that is, it is based on the use of the subsequent pages; The LRU algorithm, on the other hand, is “forward looking”, that is, based on the previous use of each page, and there is no necessary connection between the past and the future direction of the page.
Hardware support
LRU replacement algorithm is a good algorithm, but it requires more supporting hardware. In order to know how much time each page in memory is unused by a process, and how to quickly know which page is the most recent and oldest unused page, one of two types of hardware is required: registers or stacks.
register
To record the usage of each page in memory for a process, a shift register must be configured for each page in memory, which can be expressed as
R = Rn-1 rn-2 Rn-3… R2 R1 R0
When a process accesses a physical block, the R n -1 position of the corresponding register is 1. At this point, the timing signal will move the register one bit to the right at certain intervals (for example, 100 ms). If we regard the number of n-bit registers as an integer, then the page corresponding to the register with the smallest value is the most recent and longest unused page. Figure 2 shows the LRU access for a process with eight pages in memory configured with an 8-bit register for each memory page. Here, the eight memory pages are numbered from 1 to 8. As can be seen from the figure, the R value of the third memory page is the smallest. When a page is missing, it is replaced out first.
The stack
A special stack can be used to hold the page number of each page currently in use. Whenever a process accesses a page, it pushes the page number off the stack and onto the top of the stack. Therefore, the top of the stack is always the number of the most recently visited page, and the bottom of the stack is the number of the most recently unused page. Assume that the sequence of page numbers accessed by an existing process is:
4，7，0，7，1，0，1，2，1，2，6
As the process visits, the page number in the stack changes as shown in Figure 3. A missing page occurred while visiting page 6. At this point, page 4 is the most recent and longest unaccessed page and should be replaced out.
Code implementation
Train of thought
-
Map A Map is used to store information about all current nodes. The key is key and the value is a specific node in the linked list.
-
The list
Use a bidirectional linked list to record the order of the current nodes.
Linked list node data structure
Save the information about the inserted node, pre pointing to the previous node and next pointing to the next node.
const linkLineNode = function (key = "", val = "") {
this.val = val;
this.key = key;
this.pre = null;
this.next = null;
};
Copy the codeLinked list data structures
Save head and tail.
const linkLine = function () {
let head = new linkLineNode("head"."head");
let tail = new linkLineNode("tail"."tail");
head.next = tail;
tail.pre = head;
this.head = head;
this.tail = tail;
};
Copy the codeList header added
Insert the node after the header and change the next pointer of the header and the pre pointer of the next node of the original header.
linkLine.prototype.append = function (node) {
node.next = this.head.next;
node.pre = this.head;
this.head.next.pre = node;
this.head.next = node;
};
Copy the codeDelete pointer node from linked list
Redirect the next and pre points to the nodes before and after the node.
linkLine.prototype.delete = function (node) {
node.pre.next = node.next;
node.next.pre = node.pre;
};
Copy the codeDelete and return the last node of the list (non-tail)
Take the last node of the list (non-tail node), delete it and return the node information.
linkLine.prototype.pop = function () {
let node = this.tail.pre;
node.pre.next = this.tail;
this.tail.pre = node.pre;
return node;
};
Copy the codePrints linked list information
Prints the list information in sequence, taking the attributes to be printed as inputs.
linkLine.prototype.myConsole = function (key = 'val') {
let h = this.head;
let res = "";
while (h) {
if(res ! ="") res += "-- >";
res += h[key];
h = h.next;
}
console.log(res);
};
Copy the codeLRUCache data structure
Capacity Stores the maximum capacity, kvMap stores node information, and linkLine is the sequential linked list of nodes.
/ * * *@param {number} capacity* /
var LRUCache = function (capacity) {
this.capacity = capacity;
this.kvMap = new Map(a);this.linkLine = new linkLine();
};
Copy the codeget
Returns the value of the keyword if it exists in the cache and resets the node list order to move the node after the first node, otherwise -1 is returned.
/ * * *@param {number} key
* @return {number}* /
LRUCache.prototype.get = function (key) {
if (this.kvMap.has(key)) {
let node = this.kvMap.get(key);
this.linkLine.delete(node);
this.linkLine.append(node);
return node.val;
}
return -1;
};
Copy the codeput
If the keyword key already exists, change its data value value and reset the node list order to move the node after the first node; If not, the group key-value is inserted into the cache. If the number of keywords exceeds capacity due to an insert operation, you need to export the unused keywords.
/ * * *@param {number} key
* @param {number} value
* @return {void}* /
LRUCache.prototype.put = function (key, value) {
if (this.kvMap.has(key)) {
let node = this.kvMap.get(key);
node.val = value;
this.linkLine.delete(node);
this.linkLine.append(node);
} else {
let node = new linkLineNode(key, value);
if (this.capacity == this.kvMap.size) {
let nodeP = this.linkLine.pop();
this.kvMap.delete(nodeP.key);
}
this.kvMap.set(key, node);
this.linkLine.append(node); }};Copy the codeThe complete code
const linkLineNode = function (key = "", val = "") {
this.val = val;
this.key = key;
this.pre = null;
this.next = null;
};
const linkLine = function () {
let head = new linkLineNode("head"."head");
let tail = new linkLineNode("tail"."tail");
head.next = tail;
tail.pre = head;
this.head = head;
this.tail = tail;
};
linkLine.prototype.append = function (node) {
node.next = this.head.next;
node.pre = this.head;
this.head.next.pre = node;
this.head.next = node;
};
linkLine.prototype.delete = function (node) {
node.pre.next = node.next;
node.next.pre = node.pre;
};
linkLine.prototype.pop = function () {
let node = this.tail.pre;
node.pre.next = this.tail;
this.tail.pre = node.pre;
return node;
};
linkLine.prototype.myConsole = function (key = 'val') {
let h = this.head;
let res = "";
while (h) {
if(res ! ="") res += "-- >";
res += h[key];
h = h.next;
}
console.log(res);
};
/ * * *@param {number} capacity* /
var LRUCache = function (capacity) {
this.capacity = capacity;
this.kvMap = new Map(a);this.linkLine = new linkLine();
};
/ * * *@param {number} key
* @return {number}* /
LRUCache.prototype.get = function (key) {
if (this.kvMap.has(key)) {
let node = this.kvMap.get(key);
this.linkLine.delete(node);
this.linkLine.append(node);
return node.val;
}
return -1;
};
/ * * *@param {number} key
* @param {number} value
* @return {void}* /
LRUCache.prototype.put = function (key, value) {
if (this.kvMap.has(key)) {
let node = this.kvMap.get(key);
node.val = value;
this.linkLine.delete(node);
this.linkLine.append(node);
} else {
let node = new linkLineNode(key, value);
if (this.capacity == this.kvMap.size) {
let nodeP = this.linkLine.pop();
this.kvMap.delete(nodeP.key);
}
this.kvMap.set(key, node);
this.linkLine.append(node); }};Copy the codetest
var obj = new LRUCache(2);
obj.put(1.1);
obj.put(2.2);
console.log(obj.get(1)); / / -- > 1
obj.put(3.3);
console.log(obj.get(2));/ / -- > 1
obj.put(4.4);
console.log(obj.get(1));/ / -- > 1
console.log(obj.get(3));/ / -- > 3
console.log(obj.get(4));/ / -- > 4
Copy the code