LFU 算法c++的两种实现

本文主要是介绍LFU 算法c++的两种实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

描述：

实现 LFUCache 类：
LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
int get(int key) - 如果键存在于缓存中，则获取键的值，否则返回 -1。
void put(int key, int value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最久未使用 的键。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lfu-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：hash表+平衡二叉树

• 维护每个节点的使用次数以及使用时间戳，将每个节点按照使用次数、使用时间戳升序排序，删除的时候总是取第一个。
• hash表中存的是<key, Node>，用来在O(1)时间内找到想要的节点，这点与LRU思路类似
• 排序这块能想到的数据结构就是优先队列或者平衡二叉树。由于c++的优先队列不支持删除，所以使用c++的set实现。里面存的是Node，重载operator<。
• get方法O(logn)：利用hash表拿到节点，然后更新节点的使用次数以及时间戳，再从set中删除旧节点，再插入新节点
• put方法O(logn): 三种情况，1）hash表中存在key。这个时候取出节点，并且更新其value、使用次数、时间戳，然后set中删除旧节点，再插入新节点。2）hash表中不存在key，2.1）当前系统容量没有达到capacity。这个时候，创建一个新的节点，插入hash表和set即可。2.2）容量达到capacity，则取出set中的第一个节点并删除，然后再插入新节点。注意是先删再插入。

struct Node{ 
//维护每个节点的使用次数以及使用时间戳
        int key;
        int val;
        int freq;
        int time;
        Node():freq(1),time(0){};
        Node(int key, int value):key(key),val(value),freq(1),time(0){};
        bool operator< (const Node& _node)const{
            return this->freq==_node.freq?this->time<_node.time:this->freq<_node.freq;
        }
};
class LFUCache{
//    按思路一实现
public:

    int time;
    int capacity;
    int sz;
    // hash表中存的是<key, Node>，用来在O(1)时间内找到想要的节点，这点与LRU思路类似
    unordered_map<int,Node> key2node; 
    // 排序这块能想到的数据结构就是优先队列或者平衡二叉树。由于c++的优先队列不支持删除，所以使用c++的set实现。里面存的是Node，重载operator<。
    set<Node>squeue; 
    LFUCache(const int & _capacity):time(0),capacity(_capacity),sz(0){};
    int get(const int & key){ 
        //利用hash表拿到节点，然后更新节点的使用次数以及时间戳，再从set中删除旧节点，再插入新节点
        if(capacity==0) return -1;  // capacity ==0 特殊处理
        if(key2node.count(key)){ 
            Node cur = key2node[key];
            squeue.erase(cur);
            cur.freq++;
            cur.time=++time;
            key2node[key]=cur; // 值传递，需要赋值完成hash表更新
            squeue.insert(cur);
            return cur.val;

        }else{
            return -1;
        }
    }
    void put(int key, int value){
        // 三种情况，
        if(capacity==0) return; // capacity ==0 特殊处理
        if(key2node.count(key)){ 
// 1）hash表中存在key。这个时候取出节点，并且更新其value、使用次数、时间戳，然后set中删除旧节点，再插入新节点。
            Node cur = key2node[key];
            squeue.erase(cur);
            cur.freq++;
            cur.time=++time;
            cur.val=value;
            key2node[key]=cur;
            squeue.insert(cur);
        }else{
            // 2）hash表中不存在key
            Node cur(key,value);
            cur.time=++time;
            if(sz == capacity){   
  // 2.2）容量达到capacity，则取出set中的第一个节点并删除，然后再插入新节点。注意是先删再插入。

                auto delnode=squeue.begin();
                // cout << "delnode" << delnode->key << ":" << delnode->val<<endl;
                key2node.erase(delnode->key);
                squeue.erase(delnode);

            }else{
                // 2.1）当前系统容量没有达到capacity。这个时候，创建一个新的节点，插入hash表和set即可。
                sz++;
            }
            // 公共部分
            squeue.insert(cur);
            key2node[key] = cur;
        }
    }
    void print(){ //打印队列，方便调试
        for(auto node:squeue){
            printf("node key: %d, node val:%d, node freq:%d, node time:%d\n",node.key,node.val,node.freq,node.time);
        }
    }
};

思路2：hash表+hash双链表

• hash表存储<key, list<Node>::iterator>，用来在查找时以O(1)时间复杂度定位到Node
• hash双链表是unordered_map + list结合体，存储的是<freq, list<Node>> ，freq指节点使用的频率
• 利用双链表实现时间上的排序，为每个freq建立一个双链表来实现使用频率上的排序
• 使用一个minFreq来记录全局最小的使用频率，从而利用hash链表快速定位待删除的节点
• get方法O(1): 利用hash表拿到节点指针，从而获取value，freq+1，利用hash链表从原来的freq列表中删除，并插入freq+1的链表头部。还需判断freq是否需要更新
• put方法O(1): 三种情况：1）hash表中存在key，取出节点，并且更新其value、freq，利用hash链表从原来的freq列表中删除，并插入freq+1的链表头部。还需判断freq是否需要更新。2）hash表中不存在key，2.1）当前系统容量没有达到capacity，创建一个新节点，然后插入freq=1的hash链表头部，并更新minFreq，再插入到hash表中。2.2）当前系统容量达到capacity，利用minFreq在hash链表中找到对应的链表的尾节点，在hash表中删除，然后从hash链表中删除。再使用2.1的方法插入新节点。

struct Node{
    int key;
    int val;
    int freq;
    Node(){};
    Node(int _key,int _val):key(_key),val(_val),freq(1){};
};
class LFUCache{
public:
    int capacity;
    int sz;
    int minFreq;
    unordered_map<int,list<Node>::iterator> key2node;
    unordered_map<int,list<Node>> freq2list;
    LFUCache(int _capacity):capacity(_capacity),sz(0),minFreq(1){};
    int get(int key){
        if(capacity==0) return -1;
        // 通过hash表获得节点位置，如果hash表中不存在，则返回-1
        if(key2node.count(key)){
            // 取出节点地址
            auto it = key2node[key];
            // freq+1，并从原链表中移除
            int val = it->val;
            int freq = it->freq;
            freq2list[freq].erase(it);
            if(freq2list[freq].size()==0){ // 如果此时链表为空，则删除这个链表，并且判断是否需要更新minFreq
                freq2list.erase(freq);
                if(freq == minFreq){
                    minFreq = freq+1;
                }
            }
            // 创建新节点，并且加入freq+1对应的 hash链表，然后更新hash表
            Node cur(key,val);
            cur.freq=freq+1;
            freq2list[cur.freq].push_front(cur);
            key2node[key] = freq2list[cur.freq].begin();
            return val;

        }else{
            return -1;
        }
    }

    void put(int key, int value){
        if(capacity==0) return;
        // 三种情况
        // 1. hash表中存在key，则拿到旧节点，旧节点从hash链表中删除，并且将新节点插入freq+1的hash链表，更新
        // hash表，并且判断minFreq是否需要更新
        if(key2node.count(key)){
            auto it = key2node[key];
            int freq = it->freq;
            freq2list[freq].erase(it);
            if(freq2list[freq].size()==0){ // 如果此时链表为空，则删除这个链表，并且判断是否需要更新minFreq
                freq2list.erase(freq);
                if(freq == minFreq){
                    minFreq = freq+1;
                }
            }
            // 将新的节点插入freq+1对应的链表，更新hash表
            Node cur(key,value);
            cur.freq=++freq;
            freq2list[freq].push_front(cur);
            key2node[key]=freq2list[freq].begin();

        }  else{

        // hash 表中不存在，则需要创建新节点。如果容量已满需要删除应被删除的节点。
        if(sz == capacity){
            // 容量满了，先删除需要被淘汰的节点
            // 先取出需要被淘汰的节点
            Node delnode=freq2list[minFreq].back();
            // 从hash链表中删除
            freq2list[minFreq].pop_back();
            // 从hash表中删除
            key2node.erase(delnode.key);

            if(freq2list[minFreq].size()==0){
                freq2list.erase(minFreq);
                // 这里不用更新minFreq，因为后面要插入新节点肯定是1
            }


        } else{
            // 否则，sz++
            sz++;
        }
//        创建新节点
        Node cur(key,value);
        //插入hash链表
        freq2list[1].push_front(cur);
        // 更新hash表
        key2node[key]=freq2list[1].begin();
        // 更新minFreq
        minFreq=1; 
        }
    }

};

总结，相对于LRU，这个需要更新和维护的状态增加了不少，比较容易出错，面试如果遇到把思路讲讲应该就可以了。

这篇关于LFU 算法c++的两种实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！