This is the first article in the front-end also point algorithm series, and the code in the project is intended to be written entirely in TS.

The techniques covered in this article include:

  • Two-way linked list
  • Hash table (object in JS)

What:

Cache is a technology to improve the performance of data reading. It is widely used in hardware design and software development, such as CPU cache, database cache, browser cache and so on.

The size of the cache is limited. When the cache is full, what data should be purged and what data should be retained? This requires a cache elimination strategy. There are three common FIFO policies: First In, First Out (FIFO), Least Frequently Used LFU (Least Recently Used LRU).

The least recent, the more recently used, the more will not be cleared, and the furthest used will be gradually pushed to the discard end, if not used, the data will be discarded when continuous storage.

Question:

Using your knowledge of data structures, design and implement an LRU (least recently used) caching mechanism. It should support the following operations: get for data and PUT for writing data. Get (key) – Gets the value of the key if it exists in the cache (always positive), otherwise -1 is returned. Write data PUT (key, value) – Writes the data value of the key if it does not exist. When the cache reaches its maximum capacity, it should remove the least-recently used data values before writing new data to make room for new data values.

Emphasize the use of bidirectional linked list implementation

How:

  • LRU has capacity limits (capacity)
  • Get (k) values (get)
    • Returns -1 if not obtained
    • Returns, and puts the (k, v) pair to the most recently used end (removeNode,addNode)
  • Put (k, v)put)
    • If the k exists, delete it and add (k, v) to the most recently used end; if not, add (k, v) to the most recently used end.
    • If the total length is greater than the capacity after addition, remove the farthest used (k, v)

The flow chart

The initial conditions

A bidirectional linked list contains nodes as follows

class LinkedListNode {
  key: number
  value: number
  prev: LinkedListNode | null
  next: LinkedListNode | null
  constructor(key: number = 0, value: number = 0) {
    this.key = key
    this.value = value
    this.prev = null // The previous node to which the current node points
    this.next = null // The next node to which the current node points}}Copy the code

You start with just a header and a tail, and the head next points directly to the tail, and the tail prev points to the head.

The subsequent GET and PUT operations are based on node addition and node deletion. If capacity is 4, put (4, 4), (3, 3), (2, 2), (1, 1) into LRU, the list will look like this.

Get (4), the node whose key is 4 will automatically move closer to the head, and the linked list will re-establish the pointing

Put (2, 22), the node whose key is 2 is first removed from the list and then reassigned to value 22 before being added to the header

Put the process

To put, remove the node directly (removeNode) and then add it to the head (addNode). The advantage of bidirectional lists is that as soon as a node is passed in, it can automatically find the precursor and successor nodes of the node and reassign the pointer.

Deleting a node

  private removeNode(node: LinkedListNode) {
    // Save prev and next for the current node
    const prev = node.prev as LinkedListNode
    const next = node.next as LinkedListNode

    // Point the previous node to the next node of the nodenode.prev! .next = next// Point the prev of the latter node to the previous node of the nodenext! .prev = prev }Copy the code

Add a node

  private addNode(node: LinkedListNode) {
    // Set up node prev and next
    node.prev = this.head
    node.next = this.head.next

    // Set the first node to point to node before heading. Next
    this.head.next! .prev = node// Finally, redirect head's next to node
    this.head.next = node
  }
Copy the code

If you have reached the capacity of the linked list, you need to remove the nodes at the end

  private popTail(): LinkedListNode {
    const res = this.tail.prev as LinkedListNode
    // Delete a node
    this.removeNode(res)
    return res
  }
Copy the code

Put the code

  put(k: number, v: number) {
    const node = this.cache[k]
    if(! node) {// If no node is found, insert a new node
      const newNode = new LinkedListNode(k, v)
      this.cache[k] = newNode
      this.addNode(newNode)
      this.size += 1
      // Check whether capacity has been checked by size. If capacity exceeds size, delete the tail node
      if (this.size > this.capacity) {
        const popNode = this.popTail()
        delete this.cache[popNode.key]
        this.size -= 1}}else {
      // Delete the node from the list and add it to the head
      this.removeNode(node)
      node.value = v
      this.addNode(node)
    }
  }
Copy the code

Get the process

Get, if there is no value in the list, returns -1, if there is value, returns the value of the node and moves the node to the head.

Move to the header containing the two-cell process described in put, delete first and then add.

  private moveToHead(node: LinkedListNode) {
    this.removeNode(node)
    this.addNode(node)
  }
Copy the code

Get the code

  get(k: number) :number {
    const node = this.cache[k]
    if (node) {
      // If there is such a node, move it to head
      this.moveToHead(node)
      return node.value
    }
    return - 1
  }
Copy the code

Bidirectional linked list implementation

Bidirectional linked list + object implementation, bidirectional linked list has linked header and linked list tail node, easy to add and delete nodes


// List nodes
class LinkedListNode {
  key: number
  value: number
  prev: LinkedListNode | null
  next: LinkedListNode | null
  constructor(key: number = 0, value: number = 0) {
    this.key = key
    this.value = value
    this.prev = null // The previous node to which the current node points
    this.next = null // The next node to which the current node points}}type NumObj = {
  [k: number]: LinkedListNode
}

class LRUCache {
  // Head node
  head: LinkedListNode
  // The tail node
  tail: LinkedListNode
  // this is where the cache is stored
  cache: NumObj
  // LRU capacity
  capacity: number
  // The current size of LRU
  size: number

  constructor(capacity: number) {
    this.cache = {}
    this.capacity = capacity
    this.size = 0
    this.head = new LinkedListNode() // Initialize the header
    this.tail = new LinkedListNode() // Initialize the end node

    // There are only heads and tails in the initial case
    this.head.next = this.tail // Next of the header points to the tail
    this.tail.prev = this.head // The prev of the tail points to the header
  }

  // Add nodes to the head of the bidirectional list.
  private moveToHead(node: LinkedListNode) {
    this.removeNode(node)
    this.addNode(node)
  }

  @param {LinkedListNode} */
  private addNode(node: LinkedListNode) {
    // Set up node prev and next
    node.prev = this.head
    node.next = this.head.next

    // Set the first node to point to node before heading. Next
    this.head.next! .prev = node// Finally, redirect head's next to node
    this.head.next = node
  }

  /** * Delete a node * @param node {LinkedListNode} */
  private removeNode(node: LinkedListNode) {
    // Save prev and next for the current node
    const prev = node.prev as LinkedListNode
    const next = node.next as LinkedListNode

    // Point the previous node to the next node of the nodenode.prev! .next = next// Point the prev of the latter node to the previous node of the nodenext! .prev = prev }/** * delete the tail node */
  private popTail(): LinkedListNode {
    const res = this.tail.prev as LinkedListNode
    // Delete a node
    this.removeNode(res)
    return res
  }

  @param k {number} */
  get(k: number) :number {
    const node = this.cache[k]
    if (node) {
      // If there is such a node, move it to head
      this.moveToHead(node)
      return node.value
    }
    return - 1
  }

  // Insert a value
  put(k: number, v: number) {
    const node = this.cache[k]
    if(! node) {// If no node is found, insert a new node
      const newNode = new LinkedListNode(k, v)
      this.cache[k] = newNode
      this.addNode(newNode)
      this.size += 1
      // Check whether capacity has been checked by size. If capacity exceeds size, delete the tail node
      if (this.size > this.capacity) {
        const popNode = this.popTail()
        delete this.cache[popNode.key]
        this.size -= 1}}else {
      // Delete the node from the list and add it to the head
      this.removeNode(node)
      node.value = v
      this.addNode(node)
    }
  }
}
Copy the code

Get stores values from the hash table, and the time complexity of GET is O(1). Put time complexity is also O(1).

Run the test

The test pass

Compiled JS execution efficiency

Map implementation

A Map is a hash table, and the data stored in the Map is automatically sorted in sequence.

class LRUCache {
  cache: Map<number.number>
  constructor(public capacity: number) {
    this.cache = new Map()
  }
  // Get a value with key
  get(key: number) :number {
    const v = this.cache.get(key)
    if (v === undefined) {
      return - 1
    } else {
      this.moveToEnd(key, v)
      return v
    }
  }

  moveToEnd(k: number, v: number) {
    this.cache.delete(k)
    this.cache.set(k, v)
  }

  // Insert a value
  put(key: number, value: number) {
    if (this.cache.has(key)) {
      this.cache.delete(key)
    } else if (this.cache.size >= this.capacity) {
      this.cache.delete(this.cache.keys().next().value)
    }
    this.cache.set(key, value)
  }
}
Copy the code

The execution efficiency after compiling into JS code

Get is taken directly from the hash table and the time complexity is O(1). Put is taken directly to the hash table and the time complexity is O(1).

Article code link:

  • Map implementation
  • Bidirectional linked list implementation

Welcome to follow my public account Yunying Sky

Regularly parse React source code in depth