Learn these two cache design questions, let's run naked on the road of design!

preface

Recently, I tore up some design problems and found that some design problems fit well with the functions we take for granted in the development process. Some of our language features can be controlled by doing these design problems.

Here are two cache design questions, which are useful for us to think about how cache removes redundant resources. Let’s tear them up together.

Drainage of the

Now that we’ve done divide-and-conquer, we’re just getting started with the basic front-end algorithms

Learn these a few and check collection, can happily brain teaser!

Brush the 18 greedy, mother no longer have to worry about me to see greedy is afraid!

Brush these 15 tracebacks, and you’re ready for a no-brainer assault interview

Brush these two pointer questions, you can tear the front end of the interview

After brushing the 12 sliding Windows, you can tear the front end of the interview

Brush these 20 dichotomy questions, may still tear the big factory interview

Brush these a few pile of questions, or may not tear the big factory interview

Brush these 30 tree questions, may still tear the big factory interview

Brush these 20 linked list questions, may still tear the big factory interview

Brush these 15 DP questions, can only chance the topic into dachang

Brush up on these bits, and wait until you consider the job interview

The body of the

LRU – Least Recently Used: when the cache space is insufficient, the Least Recently Used buffer will be deleted.

LFU — Most Frequently Used, when the cache space is insufficient, the Least Frequently Used one is killed. If the frequency of use is the same, then according to the law of LRU, kill the least recently used;

So you can think of LFU as an advance of LRU;

It is said that Redis cache mainly uses LFU;

code

146. LRU caching mechanism

Analysis of the

Each node is represented by a bidirectional linked list, so that after get or PUT, the time complexity of the mobile node is O(1){O(1)}O(1);
Virtual heads and tails are used to ensure that the boundaries of the front and back nodes move
Each time get and PUT are used, the corresponding node is moved to the end; When map.size === capacity, you need to remove the node in the head before adding the node in the tail
Every time the get, put the time complexity is O (1) (1)} {O O (1), space complexity is O (n) (n)} {O O (n)

function ListNode(key = null, val = null) {
  this.key = key;
  this.val = val;
  this.next = null;
  this.prev = null;
}

var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.emptyHead = new ListNode();
  this.emptyTail = new ListNode();
  this.emptyHead.next = this.emptyTail;
  this.emptyTail.prev = this.emptyHead;
  this.map = new Map(a); }; LRUCache.prototype.get =function (key) {
  if (this.map.has(key)) {
    // First remove, then move to the end, then get
    const ret = this.removeAndMoveToEnd(key);
    return ret.val;
  }
  return -1;
};

LRUCache.prototype.put = function (key, value) {
  if (!this.map.has(key)) {
    // It does not exist
    if (this.map.size === this.capacity) {
      // Delete the previous one
      let node = this.emptyHead.next;
      this.map.delete(node.key); // Remove from map
      this.emptyHead.next = node.next;
      node.next.prev = this.emptyHead;
    }
    const node = new ListNode(key, value);
    // Restore the last value
    this.moveToTail(node);
    this.map.set(key, node);
  } else {
    // Node is the previous node, but put may have changed the corresponding val
    const node = this.removeAndMoveToEnd(key); node.val = value; }}; LRUCache.prototype.removeAndMoveToEnd =function (key) {
  // It already exists. Delete it and move it to the end
  let node = this.map.get(key);
  / / remove first
  node.prev.next = node.next;
  node.next.prev = node.prev;
  // Move to the back
  this.moveToTail(node);
  return node; / / the return value
};

LRUCache.prototype.moveToTail = function (node) {
  node.prev = this.emptyTail.prev;
  node.next = this.emptyTail;
  this.emptyTail.prev.next = node;
  this.emptyTail.prev = node;
};

Copy the code

460. LFU cache – Least frequently used cache

Analysis of the

Cache freqMap, key is frequency, value is bidirectional linked list at this frequency;
Cache nodeMap, where key is the key put in and value is the node of the bidirectional list
The reason why freqMap is used to cache the linked list with the same frequency is to quickly find the list with the smallest frequency minFreq when the cache capacity exceeds, and then insert the least frequently used nodes in the list with the smallest frequency (the head of the list — is inserted behind the list every time, so at the same frequency, The first to be added was the header node.
Here we need to build a bidirectional linked list DLinkList and a bidirectional linked list Node
When we actually start the LFU cache, it needs at least the following attributes: Capacity memory size, size used size, minFreq minimum frequency in the cache, then nodeMap and freqMap

LFU operation — get obtain

When performing the cache GET operation, we need to determine whether the node is already cached in the nodeMap, if not, return -1, if so, fetch the node node
Because the Node node performs the GET operation, it needs to be performed on this nodeL frequency operationIs to increase the frequency at which this node is already used

LFU auxiliary function – insFreq frequency – up operation

The input parameter is the node whose frequency needs to be raised. We first get its frequency freq, and then extract the current linked list oldLinklist of this node from freqMap.
Since this node needs to be increased in frequency, it needs to be removed from oldLinklist;
After removal we need to consider whether this node is the only one in the lowest frequency list in the cache. If so, we need to increase minFreq for the entire LFU cache
After processing the old operation, start to increase the frequency, first node.freq +1, then find the link list newLinklist, then insert node node; Or create a bidirectional linked list, insert node, and update freqMap.

LFU operation — PUT to obtain

Check whether the inserted node already exists, if so, update the node value, and then proceed to the nodeL frequency operationCan be
If haven’t insert, the first to determine whether the cache is full (enclosing size = = = this. Capacity) to the console. The log (minFreqDLinkList, enclosing freqMap. Get (2))
If the memory is full, you need according to the latest frequency minFreq cache first find out the corresponding list minFreqDLinkList, take out the chain table real head node minFreqDLinkList. Head. Next, and at the same time, it have to be deleted in nodeMap, The corresponding cache can be lowered
Create a newNode newNode with frequency 1, or create one and insert the newNode. If it is a new list, update the freqMap.
Finally, I need to update minFreq to 1 and add this.size

/** * @bidirectional linked list node */
 function Node(key,value) {
    this.key = key
    this.value = value
    this.freq = 1; // Cache the operation frequency of the current node, which was 1 when it was initially created
    this.prev = null 
    this.next = null
}

/** * @define a bidirectional list * 1. removeNode: remove an input node from the list * 2. appendNode: insert a node at the end of the list * 3. Note that the bidirectional list is a list with a virtual guard, so get the real header as this.head. Next and the real tail as this.tail.prev */
function DLinkList(){
    this.head = new Node()
    this.tail = new Node()
    this.head.next = this.tail
    this.tail.prev = this.head
}
// 
DLinkList.prototype.removeNode = function(node) {
    node.prev.next = node.next
    node.next.prev = node.prev
}
DLinkList.prototype.appendNode = function(node) {
    node.next = this.tail
    node.prev = this.tail.prev
    this.tail.prev.next = node
    this.tail.prev = node
}


var LFUCache = function(capacity) {
    this.capacity = capacity
    this.size  = 0 // This is the list length, the maximum capacity
    this.minFreq = 0 // Minimum frequency of use
    this.nodeMap = new Map(a)this.freqMap = new Map(a)// Cache frequency bidirectional linked list
};

LFUCache.prototype.get = function(key) {
    if(!this.nodeMap.has(key)){
        return -1
    }
    const node = this.nodeMap.get(key)
    // Increase the frequency of this node
    this.insFreq(node)
    return node.value
};

LFUCache.prototype.put = function(key, value) {
    if(this.capacity === 0) {return 
    }

    const node = this.nodeMap.get(key)
    if(node) {
        // If the node already exists, increase the frequency
        node.value = value
        this.insFreq(node)
    }else{
        // If the cache has been exceeded
        if(this.size === this.capacity){
            // Get the minimum frequency bidirectional list
            const minFreqDLinkList =this.freqMap.get(this.minFreq)
            console.log(minFreqDLinkList,this.freqMap.get(2))
            // Kill the first one
            this.nodeMap.delete(minFreqDLinkList.head.next.key)
            minFreqDLinkList.removeNode(minFreqDLinkList.head.next)
            this.size--
        }
        // Then the new node is processed
        const newNode = new Node(key,value)
        this.nodeMap.set(key,newNode)
        // go beyond the bidirectional list with frequency 1
        if(this.freqMap.has(1)) {const newLinklist = this.freqMap.get(1)
            newLinklist.appendNode(newNode)
        }else{
            // If there is no list for this frequency, create one
            const newLinklist = new DLinkList()
            newLinklist.appendNode(newNode)
            this.freqMap.set(1,newLinklist)
        }
        this.size++
        this.minFreq = 1 // This is the minimum minimum frequency}};/** * @parse -- increase node frequency * 1. Remove the frequency from the original bidirectional list, add one and insert it into the new bidirectional list */
LFUCache.prototype.insFreq = function(node) {
    let freq = node.freq
    // Get the old frequency bidirectional list
    const oldLinklist = this.freqMap.get(freq)
    // Remove node from the list
    oldLinklist.removeNode(node)
    // After removal, we need to consider whether the value of the minimum frequency will be updated
    // 1. The minimum frequency is the old frequency
    // 2. There are no nodes in the old frequency chain
    // Then you need to update the minimum frequency
    if(freq === this.minFreq && oldLinklist.head.next === oldLinklist.tail){
        this.minFreq = freq+1
    }

    // Continue processing
    freq++
    node.freq = freq
    if(this.freqMap.has(freq)){
        // Find the list of new frequencies, if any
        const newLinklist = this.freqMap.get(freq)
        // Add a node to the list
        newLinklist.appendNode(node)
    }else{
        // Create a new one
        const newLinklist = new DLinkList()
        newLinklist.appendNode(node)
        this.freqMap.set(freq,newLinklist)
    }
}
Copy the code

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Learn these two cache design questions, let’s run naked on the road of design!

preface

The body of the

code

146. LRU caching mechanism

460. LFU cache – Least frequently used cache

Learn these two cache design questions, let’s run naked on the road of design!

preface

The body of the

code

146. LRU caching mechanism

460. LFU cache – Least frequently used cache

Related Posts

Cyclomatic complexity stuff – Front-end Code Quality series (Part 2)

React in Patterns is here in Chinese

Next-generation CSS: @Container