LRU/LFU

LRU 缓存

LRU简介

LRU（Least Recently Used）是一种常见的缓存淘汰策略，用于在有限的内存空间中存储最近最常使用的数据。当缓存达到其容量上限时，最近最少使用的数据将从缓存中淘汰。
缺点：
对于偶发的批量操作，比如批量查询历史数据，就有可能使缓存中热门数据被这些历史数据替换，造成缓存污染，导致缓存命中率下降，减慢了正常数据查询。

代码实现哈希表+双向链表

class LRUCache {
public:
    struct ListNode{
        int key,value;
        ListNode *next;
        ListNode *prev;
        ListNode():key(0),value(0),next(nullptr),prev(nullptr){}
        ListNode(int k,int v):key(k),value(v),next(nullptr),prev(nullptr){}
        ListNode(int k,int v,ListNode*next,ListNode *prev):key(k),value(v),next(next),prev(prev){}
    };
    LRUCache(int capacity):size(capacity){
        vhead = new ListNode();
        tail = new ListNode();
        vhead->next = tail;
        tail->prev=vhead;
    }
    
    int get(int key) {
        auto it=ha.find(key);
        if(it!=ha.end()) {
            ListNode *te = it->second;
            if(vhead->next!=te){
                del_inser(te,vhead);
            }
            return te->value;
        }
        return -1;
    }
    
    void put(int key, int value) {
        auto it=ha.find(key);
        if(it!=ha.end()) {
            ListNode *te = it->second;
            te->value=value;
            del_inser(te,vhead);
        }
        else{
            if(ma.size()==size) {
                ListNode *te = tail->prev;
                auto it = ha.find(te->key);
                ha.erase(it);
                del(te);
                delete te;
                te=nullptr;
            }
            ListNode *node = new ListNode(key,value);
            insert(node,vhead); 
            ha.insert(pair<int,ListNode*>(key,node));
        }
    }
private:
    void insert(ListNode *node,ListNode *cur){
        node->next=cur->next;
        cur->next=node;
        node->prev=cur;
        node->next->prev=node; 
    }
    void del(ListNode *node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    void del_inser(ListNode *node,ListNode *cur){
        del(node);
        insert(node,cur);
    }
private:
    //hash表+单向链表
    int size;//容量
    unordered_map<int,ListNode*> ha;
    ListNode *vhead;//虚拟头节点
    ListNode *tail;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

LFU缓存

LFU算法是一种基于访问频次的缓存淘汰算法，它会根据数据的历史访问频率来淘汰数据。LFU算法的优点是在数据访问符合正态分布时，相比于LRU算法，LFU算法的缓存命中率会高一些。但是LFU算法的复杂度要比LRU更高一些，需要维护数据的访问频次，每次访问都需要更新 。

哈希表+平衡树

首先需要定义一个节点的结构

struct node{
	int key,value,freq,time;
	node(int k,int v,int f,int t):key(k),value(v),freq(f),time(t){}
	bool operator<(const node&rhs){
		return freq==rhs.freq?time<rhs.time:freq<rhs.freq;
	}
};
1
2
3
4
5
6
7

哈希表用来存储key到node之间的映射关系，这样通过key找到node的时间复杂度为O(1)
平衡树set用来存储node，并且按照第一关键字为freq，第二关键字为time从小到大进行排序。

对于get操作，首先在哈希表中进行寻找若找不到则返回-1。找到的情况下，在平衡树中删除该节点修改freq和node的值，重新插入平衡树，修改哈希表中的映射关系，返回节点的value值。

对于put操作。首先在哈希表中寻找该节点，找不到：
若当前元素个数小于容量，构建新的节点并插入。元素个数等于容量，先根据规则删除元素也就是删除平衡树中的第一个节点，之后插入新的节点。找得到：修改value的值，接下来的操作和get操作一致

class LFUCache {
public:
    LFUCache(int capacity):cap(capacity),time(0){
        se.clear();
        ma.clear();
    }
    
    int get(int key) {
        if(cap==0) return -1;
        auto it = ma.find(key);
        if(it==ma.end()) return -1;
        node te=it->second;
        del_inser(se,ma,te);
        return te.value;
    }
    
    void put(int key, int value) {
        if(cap==0) return;
        auto it = ma.find(key);
        if(it!=ma.end()){
            node te=it->second;
            te.value = value;
            del_inser(se,ma,te);
        }else {
            if(ma.size()==cap){
                ma.erase(se.begin()->key);
                se.erase(se.begin());
            }
            node nd(key,value,1,++time);
            se.insert(nd);
            ma.insert(make_pair(key,nd));
        }
    }
private:
    struct node{
        int key,value,freq,time;
        node(){}
        node(int k,int v,int f,int t):key(k),value(v),freq(f),time(t){}
        bool operator<(const node&rhs)const{
            return freq!=rhs.freq?freq<rhs.freq:time<rhs.time;
        }
    };
    void del_inser(set<node>&se,unordered_map<int,node>&ma,node&it){
        se.erase(it);
        it.freq+=1;
        it.time=++time;
        se.insert(it);
        ma[it.key]=it;
    }
private:
    set<node>se;
    unordered_map<int,node>ma;
    int cap;
    int time;
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

时间复杂度分析。对于get操作，从哈希表中获取元素为O(1)，从平衡树中删除更新重新插入的操作为O(logn)总体的时间复杂度为O(logn)；对于put操作，O(logn)
空间复杂度分析，O(capcaity)

双哈希表

第一个哈希表key_table记录key与双向链表中节点所在的位置。第二个哈希表freq_table记录freq与对应双向链表之间的映射。一个freq对应一个双向链表是为了保证get和put操作的时间复杂度为O(1)。但是还要额外记录一个变量minfreq记录节点的最小使用频率。为了删除操作做准备。

对于get操作，首先根据key在key_table中找到对应的链表节点，找不到返回-1。找到的话，首先记录当前节点的freq并删除freq_table[freq]对应的链表中的该节点，删除之后还要判断当前链表是否为空，链表为空删除该链表，如果链表为空并且当前的freq==minfreq则将minfreq+1。然后根据key value freq+1重新构造一个新的节点并将其插入freq_table[freq+1]的链表的头部。

对于put操作，如果能够根据key在key_table中找到节点则跟get操作一样但是要修改节点的value值。如果没有找到，如果当前元素个数等于容量，则先删除freq_table[minfreq]链表的尾部节点，删除之后链表为空删除链表，之后新建节点(新建节点的freq为1)插入freq_table[1]的链表的头部，并将minfreq设置为1。

class LFUCache {
public:
    LFUCache(int capacity):minfreq(0),cap(capacity){
        key_table.clear();
        freq_table.clear();
    }
    
    int get(int key) {
        if(cap==0)return -1;
        auto it =key_table.find(key);
        if(it==key_table.end()) return -1;
        list<Node>::iterator node=it->second;
        int freq=node->freq;int val=node->value;
        freq_table[freq].erase(node);
        if(freq_table[freq].empty()){
            freq_table.erase(freq);
            if(minfreq==freq) ++minfreq;
        }
        //这里的代码一直报错说我的node数据类型不兼容，检查了好久才发现，我前面定义了一个
        //list::iterator node=it->second;与struct node发生冲突，而且局部变量对全局变量有覆盖作用，所以一直报错。所以将struct node改成struct Node;
        freq_table[freq+1].push_front(Node(key,val,freq+1));
        key_table[key]=freq_table[freq+1].begin();
        return val;
    }
    
    void put(int key, int value) {
        if(cap==0) return;
        auto it=key_table.find(key);
        if(it!=key_table.end()){
            list<Node>::iterator node=it->second;
            int freq=node->freq;
            freq_table[freq].erase(node);
            if(freq_table[freq].size()==0){
                freq_table.erase(freq);
                if(minfreq==freq) ++minfreq;
            }
            freq_table[freq+1].push_front(Node(key,value,freq+1));
            key_table[key]=freq_table[freq+1].begin();
        }else{
            if(cap==key_table.size()){
                auto it = freq_table[minfreq].back();
                key_table.erase(it.key);
                freq_table[minfreq].pop_back();
                if(freq_table[minfreq].empty()){
                    freq_table.erase(minfreq);
                }
            }
            minfreq=1;
            freq_table[1].push_front(Node(key,value,1));
            key_table[key]=freq_table[1].begin();
        }
    }
private:
    struct Node{
        int key,value,freq;
        Node(){}
        Node(int k,int v,int f):key(k),value(v),freq(f){}
    };
private:
    int minfreq,cap;
    unordered_map<int,list<Node>::iterator> key_table;
    unordered_map<int,list<Node>> freq_table;
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

总结

LRU算法更加关注数据的访问时间，而LFU算法更加关注数据的访问频率。因此，在实际应用中，需要根据具体的业务场景来选择合适的缓存淘汰算法。