Niuke network: Design LRU cache structure design LFU cache structure

Catalog

1. Design LRU Cache structure

Get

Set

2. Design LFU Cache structure

Get

Set

Update

---

1. Design LRU Cache structure

  This question , Tell the truth , At first, I didn't understand what his input was ...

Look at the instructions , It seems like this again , It is to create a class and directly call the methods inside ：

In fact, it is to maintain a two-way linked list , Yes XV6 The memory and lock of the operating system should be known by students LRU What the hell is that? . The idea is as follows ：

Whole LRU Maintain a linked list and a hash table , Linked list can be used directly list Double linked list , Hash table with unordered_map To design , The hash table stores key And the iterator in the linked list .

Get

First , about get operation , The function is like this ： For a given key, We want to check whether it exists in the linked list , Here hash can be implemented O(1) Cost of searching time , The process is as follows ：

1. Find if it exists key Corresponding node , If not, return directly to -1

2. otherwise , Let's start with key Get the corresponding node from the hash , Then delete the corresponding node .

the reason being that LRU, So we should put the most recently used ones at the top （ Although the hash table is used, it is based on LRU We still have to put our ideas at the front ）, So we put the extracted node in the head of the linked list , And then create in the hash table <key, list.begin()> The mapping relation of .

Finally, the header node is returned value

Set

about set operation , The function is like this ： For a given <key, value>, If it exists in the linked list key The node of , Then modify it and put it in the chain header , If it doesn't exist , Then directly add the node in front as the chain header , Also consider whether the linked list will explode , If the capacity has reached , So according to LRU Principles , Let's delete the tail of the linked list first

The code is as follows ：

class Solution {
public:
    list<pair<int, int>> dlist;
    unordered_map<int, list<pair<int, int>>::iterator> map;
    int cap;
    
    Solution(int capacity){
        cap=capacity;
    }
    
    
    int get(int key) {
         // write code here
        if(map.count(key)){
            auto tmp=*map[key];
            dlist.erase(map[key]);
            dlist.push_front(tmp);
            map[key]=dlist.begin();
            return dlist.front().second;
        }
        return -1;
    }
    
    void set(int key, int value){
         if(map.count(key)){
            dlist.erase(map[key]);
         }else if(cap==dlist.size()){
            auto tmp=dlist.back();
             map.erase(tmp.first);
             dlist.pop_back();
         }
            dlist.push_front(pair<int, int>(key, value));
             map[key]=dlist.begin();        
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* solution = new Solution(capacity);
 * int output = solution->get(key);
 * solution->set(key,value);
 */

Of course , In addition to using the data structure in the standard library , We can also create a two-way linked list by ourselves , We need to isolate a function that moves the node to the header , So that when we are doing get Operation found a node , perhaps set The corresponding node is placed in the header .

The code is as follows , There are many details to pay attention to , It mainly updates the data structure and hash ：

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int key;
    int val;
    Node *prev;
    Node *next;
    Node(int key, int val) : key(key), val(val), next(NULL), prev(NULL) {}
};

class Solution {
public:
    unordered_map<int, Node*> hash;
    Node *head;
    Node *tail;
    int cap;
    int size;
    Solution(int capacity){
        head=NULL;
        tail=NULL;
        cap=capacity;
        size=0;
        hash.clear();
    }
    //  Put a node in the header 
    //  If at the tail   The tail node needs to be updated 
    //  After moving to the header, you need to update the pointer and the header node 
    void removeToHead(Node *p){
        //  The first change 
        if(p==head){
            return;
        }
        p->prev->next=p->next;
        if(p==tail){
            tail=p->prev;
        }else{
            p->next->prev=p->prev;
        }
        p->prev=NULL;
        p->next=head;
        head->prev=p;
        head=p;
        return;
    }

    int get(int key) {
        if(hash.find(key)==hash.end()){
            return -1;
        }
        removeToHead(hash[key]);
        return hash[key]->val;
    }

    void set(int key, int value){
        if(hash.find(key)!=hash.end()){
            hash[key]->val=value;
            removeToHead(hash[key]);
        }else if(size>=cap){
            // Update the tail node to the current node   Move to the head 
            // Update hash table   Delete the original   Add new 
            int k=tail->key;
            hash.erase(k);
            tail->key=key;
            tail->val=value;
            removeToHead(tail);
            hash[key]=head;
        }else{
            // No node exists   And the capacity is not full   Insert directly into the head 
            Node *node=new Node(key, value);
            if(head==NULL){
                head=tail=node;
            }else{
                node->next=head;
                node->prev=NULL;
                head->prev=node;
                head=node;
            }
            hash[key]=head;
            size++;
        }

    }
};

2. Design LFU Cache structure

above LRU Is the least recently used strategy ,LFU yes least frequently used, Literally, it seems to be the least used strategy recently , But from the title , Yes, let's also record the use of set and get The number of times .

We use a double hash table to solve this problem , At the same time, I saw a well drawn picture in the solution ：

This is the data structure we want to maintain . First , For each frequency , We maintain a two-way linked list , This bi-directional linked list represents the set of nodes with corresponding frequencies , What's stored is {freq, key, value}, This forms a hash table of frequencies and linked lists . Based on this hash table, we can easily find the two-way linked list according to frequency , When the capacity is insufficient, it is very fast to find the deleted node . Secondly, it is also convenient for some update operations to delete inserts . It is also due to deleting nodes when the capacity is insufficient , We need a variable to store freq The smallest node .

The second hash table is key And the hash table of linked list nodes , This hash table is for get Operation is very necessary .

Next, analyze get and set The process of operation ：

Get

get The function of the operation is based on key look for value, With the hash table , We can directly base on key Find the corresponding node , And then find value, Return if not found -1.

Set

set The function of the operation is to set <key, value>, The process is as follows ：

1. If this mapping relationship existed before , So let's update the mapping , About what updates are , Then say .

2. If it doesn't exist , We are going to insert this new mapping , Of course , Also consider whether the current linked list is full , So we also need to maintain a variable that records the remaining space .

a. If it's already full , We need to do something ：

First, find the node with the lowest frequency and the least use , For the node with the lowest frequency , Since we maintain the frequency and the hash of the set of corresponding nodes , We'll soon find , For minimum use , Each time we update it, we put it in the header , So the last node is the least used .

After finding the node, we need to delete it , After deletion, we have to check whether the linked list is empty , If it is empty, you have to delete the mapping item directly .

b. If it's not full , Let's maintain the remaining capacity

And then directly to freq=1 Insert a new... Into the head of the two-way linked list <freq=1, key, value>, After that, the corresponding <key,value> mapping .

Update

The update operation is used in set There is already a corresponding key Or, for an existing node get when , Update its frequency .

First , We according to the key Take out the linked list node , Then according to the... In the linked list node freq Find the corresponding linked list , Then directly delete the corresponding node in the linked list .

If the linked list becomes empty after deletion ：

Delete the mapping relationship , Let's see if we need to update the minimum frequency , If the deleted list is the list corresponding to the minimum frequency , So it needs to be updated

Finally the new <freq+1,key,value> Insert the corresponding linked list , If it is set It needs to be updated map

The specific code is as follows ：

class Solution {
public:
    /**
     * lfu design
     * @param operators int integer vector<vector<>> ops
     * @param k int integer  the k
     * @return int integer vector
     */
    //  Store the frequency and the dictionary of the node linked list corresponding to the frequency 
    unordered_map<int, list<vector<int>>> freq_mp;
    //  Save the corresponding key value and node 
    unordered_map<int, list<vector<int>>::iterator> mp;
    //  Record the minimum frequency   To use LFU Policy find node 
    int min_freq=0;
    //  Remaining storage capacity 
    int size=0;
    
    vector<int> LFU(vector<vector<int>>& operators, int k){
        vector<int> res;
        size=k;
        for(int i=0;i<operators.size();++i){
            if(operators[i][0]==1){
                set(operators[i][1], operators[i][2]);
            }else{
                res.push_back(get(operators[i][1]));
            }
        }
        return res;
    }
    
    void update(list<vector<int>>::iterator iter, int key, int value){
        // Take a node from the bidirectional linked list   namely  vector<int>
        int freq=(*iter)[0];
        freq_mp[freq].erase(iter);
        // If there are no nodes in the frequency 
        // Delete the corresponding linked list in the frequency bidirectional linked list 
        // See if you need to update the minimum frequency 
        if(freq_mp[freq].empty()){
            freq_mp.erase(freq);
            if(freq == min_freq){
                min_freq++;
            }
        }
        // towards freq+1 In the head of the bidirectional linked list 
        // Because the original node no longer exists   It needs to be reset <key,value> The storage 
        freq_mp[freq+1].push_front({freq+1, key, value});
        mp[key]=freq_mp[freq+1].begin();
    }
    
    void set(int key, int value){
        auto it=mp.find(key);
        if(it!=mp.end()){
            // There are nodes in the linked list   to update value And frequency 
            update(it->second, key, value);
        }else{
            // The node does not exist in the hash table 
            // If the list is full   The most frequent and earliest deletion 
            // Delete the last node in the frequency table 
            // Delete the corresponding <key,value> The node of 
            if(size==0){
                int oldkey=freq_mp[min_freq].back()[1];
                freq_mp[min_freq].pop_back();
                if(freq_mp[min_freq].empty()){
                    freq_mp.erase(min_freq);
                }
                mp.erase(oldkey);
            }else{
                // Under capacity   You can directly join 
                size--;
            }
            min_freq=1;
            freq_mp[1].push_front({1, key, value});
            mp[key]=freq_mp[1].begin();
        }
    }
    
    //get operation : If not found, return -1
    // If found, update the frequency and take out value return 
    int get(int key){
        int res=-1;
        auto it = mp.find(key);
        if(it==mp.end()){
            return res;
        }
        auto iter = it->second;
        res=(*iter)[2];
        update(iter, key, res);
        return res;
    }
};

Have to say , The combination of data structure and corresponding storage is really a clever thing ~