preface

LRU is an operating system page replacement algorithm, which is the abbreviation of Least Recently Used. It is Used to eliminate pages that have been Used the longest since the last time. It can be regarded as an algorithm implemented by the operating system to replace the cache when the cache is full. The LRU algorithm is also used in the KEEP-alive component of VUE. Common page replacement algorithms are FIFO(first-in, first-out), clock (clock) and so on.

The following simulated LRU algorithm gives an example of page replacement:

  1. If the current cache is not full, insert backwards.

  2. In step 5, I thought I could not find the page address with the page address stream of 5 in the cache, and the cache was full, so I needed to select a suitable page to replace the inserted page. To sort the pages in the least recently used order, the page numbers are 3, 2, and 1, so the eliminated page is 3.

  3. The following operations are the same as the previous, are in the cache to find if there is also, if not the page replacement.

    Here is to achieve a page replacement algorithm.

Implementation approach

Our purpose is to find out that part of the least recently used and put it to replace, a relatively rough method is to use timestamp to tag and then compare each memory block timestamp, but it takes O (n) * * * * time to compare the size of the timestamp, once the volume up to compare more time will increase.

The most popular way to optimize an algorithm is to swap space for time, which we use hereDouble linked list + the MapTo implement the LRU algorithm. The data structure is designed as follows:The specific algorithm flow chart is as follows:

Code implementation

  1. Implementation of nodes

Use an instance of a class to represent a node with the following data:

  • The current key
  • The current value
  • The head pointer
  • The tail pointer
class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null; }}Copy the code
  1. The realization of the LRU
class LRU_TAG {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(a);this.head = new Node(null.null);
    this.tail = new Node(null.null);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  
  put(key, value) {}
  
  get(key){}}Copy the code

The constructor first passes capacity as the size of the list, and then uses two sentinels to represent the head and tail of the list, so that we only care about the general case.

  1. Implementation of the put function
put(key, value) {
  const node = this.map.get(key);
  // If the node already exists
  if (node) {
    node.value = value;
    // Move the node to the head of the list
    this.removeAndInsert(node);
  } else {
    const temp = new Node(key, value);
    // If the list is full
    if (this.map.size >= this.capacity) {
      this.map.delete(this.tail.prev.key);
      this.tail.prev = this.tail.prev.prev;
      this.tail.prev.next = this.tail;
    }

    this.map.set(key, temp);
    temp.next = this.head.next;
    this.head.next = temp;
    temp.prev = this.head; temp.next.prev = temp; }}Copy the code

First look for a key in the map, then confirm that the list is full, if it is, remove the last node of the list, and insert a new node at the head.

  1. The implementation of get function
get(key) {
  const node = this.map.get(key);
  if (node) {
    // Move the node to the head of the list
    this.removeAndInsert(node);
    return node.value;
  }
  return null;
}
Copy the code
  1. The implementation of removeAndInsert
removeAndInsert(node) {
    if (node === this.head.next) return;
    node.prev.next = node.next;
    node.next.prev = node.prev;

    node.next = this.head.next;
    node.next.prev = node;
    node.prev = this.head;
    this.head.next = node;
  }
Copy the code

The complete code

class LRU_TAG {
  constructor(capacity) {
    this.capacity = capacity >= 1 ? capacity : 1;
    this.map = new Map(a);this.head = new Node(null.null);
    this.tail = new Node(null.null);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  put(key, value) {
    const node = this.map.get(key);
    // If the node already exists
    if (node) {
      node.value = value;
      // Move the node to the head of the list
      this.removeAndInsert(node);
    } else {
      const temp = new Node(key, value);
      // If the list is full
      if (this.map.size >= this.capacity) {
        this.map.delete(this.tail.prev.key);
        this.tail.prev = this.tail.prev.prev;
        this.tail.prev.next = this.tail;
      }

      this.map.set(key, temp);
      temp.next = this.head.next;
      this.head.next = temp;
      temp.prev = this.head; temp.next.prev = temp; }}get(key) {
    const node = this.map.get(key);
    if (node) {
      // Move the node to the head of the list
      this.removeAndInsert(node);
      return node.value;
    }
    return null;
  }

  / * * * *@param node {Node}
   */
  removeAndInsert(node) {
    if (node === this.head.next) return;
    node.prev.next = node.next;
    node.next.prev = node.prev;

    node.next = this.head.next;
    node.next.prev = node;
    node.prev = this.head;
    this.head.next = node; }}class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null; }}Copy the code

conclusion

Using the above LRU algorithm code can search and delete nodes in O(1) time. The advantage of LRU lies in the maintenance of hot data, but LRU has poor adaptability to batch data. For example, if a batch of data is frequently inserted, the linked list will be changed in and out frequently, resulting in cache pollution.