LFU缓存 C++实现

LFU缓存

LFU 最不经常使用
least frequently used (LFU) page-replacement algorithm)。

请你为 最不经常使用(LFU)缓存算法设计并实现数据结构。它应该支持以下操作:get 和 put。

get(key) – 如果键存在于缓存中,则获取键的值(总是正数),否则返回 -1。
put(key, value) – 如果键不存在,请设置或插入值。当缓存达到其容量时,则应该在插入新项之前,使最不经常使用的项无效。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,应该去除 最近 最少使用的键。
「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。

进阶:
你是否可以在 O(1) 时间复杂度内执行两项操作?

题目来源:2020-4-5 leetcode每日

不得不说力扣这个每日题目还是不错的。不过当时太累了当天没有做这个。实际上这种思路清晰之后复杂的模拟我特别喜欢写,毕竟方方面面都考虑周到是我所追求的阿。后面也一直在准备刷题,尤其是为了头条的一面,本来LFU都在计划上了,但临时又改成了多刷几道题。结果真到了面试,面试官一道题也没让我写,全程设计题,其中就包括了这个LFU。。

回想起来设计的东西并不难,自己的思路也没差,只是因为没见到过真容,又保持着敬畏的心,总想着这东西肯定会更巧妙一些。所以有些思路没有深挖下去。当然了我觉着让我自己慢慢造这样的设计题轮子的话,我应该能造出来。不过我的造的过程可能不会一开始就想的很清楚,而是不断迭代的造出来。但敢保证这轮子稳定又好用,因为每一步都会深入的考虑各种情况,并做实验去验证。

源码如下:

hash表 + 红黑树 get put时间复杂度O(logn)

首先最近最少使用,还要删除操作,很容易就想到用平衡二叉树来实现,就是平衡二叉树的最左节点嘛。


struct Node1{ int cnt; int time; int key,value; // 实现一个比较函数,cnt为第一关键字,time(最近一次使用的时间)作为第二关键字 Node1(int cnt,int time,int key,int value):cnt(cnt),time(time),key(key),value(value){} bool operator < (const Node1& rhs)const{ return cnt== rhs.cnt? time < rhs.time: cnt < rhs.cnt; } }; class LFUCache1{ int capacity,time; unordered_map<int,Node1> key_table; set<Node1>st; public: LFUCache1(int capacity){ this->capacity = capacity; time = 0; key_table.clear(); st.clear(); } int get(int key){ if(capacity == 0) return -1; auto it = key_table.find(key); if(it == key_table.end()) return -1; Node1 cache = it->second; st.erase(cache); cache.cnt +=1; cache.time = ++time; // 记录时间戳 st.insert(cache); it->second = cache; return cache.value; } void put(int key,int value){ if(capacity == 0) return; auto it = key_table.find(key); if(it == key_table.end()){ // 如果达到缓存容量上限 if(key_table.size() == capacity){ // 从哈希和平衡二叉树中删除最近最少使用的缓存 key_table.erase(st.begin()->key ); st.erase(st.begin()); } Node1 cache = Node1(1,++time,key,value); key_table.insert(make_pair(key, cache)); st.insert(cache); }else{ Node1 cache = it->second; st.erase(cache); cache.cnt += 1; cache.time = ++time; cache.value = value; st.insert(cache); it->second = cache; // 这样就更新了hashmap啊 } } };

双哈希表 get put时间复杂度O(1)

正解,双哈希表

两个哈希表, 
第一个 freq_table 以频率为索引,每个索引放一个双向链表,这个链表里存放所有使用频率为freq_的缓存,缓存里 key,value,freq。
第二个 key_table 以key为索引,每个索引存放对应缓存再 freq_table中链表的内存地址,这样我们就能利用
两个哈希表来使得两个操作的时间复杂度均为O(1),同时需要记录一个当前缓存最少使用频率minFreq,这是为了删除操作服务的。

对于get(key)操作,我们能通过索引key 在keytable中找到缓存freq_table的链表内存地址,如果不存在直接返回-1,否则我们能获取到对应的缓存的相关信息,这样我们就能知道缓存的键值 还有使用频率,直接返回key对应的值即可。

get操作后,缓存的使用频率加一,所以我们需要更新缓存在哈希表 freq_table中的位置。 已知这个缓存的键key,值value,以及使用频率freq

那么该缓存应该存放到freq_table中 freq +1 索引下的链表中。所以我们在当前链表O(1)删除缓存对应节点,根据情况更新minFreq的值,
然后将其O(1)插入到freq+1 索引下的链表头完成更新。 操作复杂度O(1). 插入到链表头是为了保证缓存再当前链表中,从链表头到链表尾的插入时间是有序的。为删除服务。

put(key,value)操作,我们先通过索引key在key_table中查看是否有对应缓存,如果有,等价于 get,只是需要更新value。
如果没有,则相当于新加入的缓存,如果满了,则先删除再插入。

先考虑插入,由于是新插入,所以缓存频率是1,将缓存信息插入freq_table中,1索引下的列表头,同时更新key_table[key]. minFreq =1

删除操作,由于维护了minFreq,所以我们能知道freq_table里目前最少使用频率的索引,同时因为保证了链表头到链表尾插入时间是有序的
所以freq_table[minFreq]链表尾部节点 即为 使用频率最小,且插入时间最早的节点。我们删除它的同时,根据情况更新minFreq。

当时看了这一串解析真的头大了,上面是我看力扣题解的时候,边抄边理解的内容。我试着总结一下。

首先一个哈希表
unordered_map<int,list<Node>::iterator> key_table;

通过key,获取指针,这个跟LRU一样。

然后另一个哈希表, 键是频率,值是该频率对应的一条链表。(所有为该使用频率的节点都在这个链表上,链表我们有序插入)
unordered_map<int,list<Node>> freq_table;

还有一个全局变量minFreq,存储当前最小的使用频率是啥。

想出来这个数据结构,具体putget我觉着就比较好写了,慢慢琢磨就能写出来了。

当时和面试官讨论的时候,结构我猜想的和这个正解是一样的,只是具体到如何更新最小频率,如何保证O(1)的效率上,一想到情况比较复杂,我就没有再深挖下去,且自己并没有确定设计的这个结构是对的。抗压能力还需要提高。


struct Node{ int key,val,freq; Node(int key,int val,int freq):key(key),val(val),freq(freq){} }; class LFUCache{ int minfreq, capacity; unordered_map<int, list<Node>:: iterator> key_table; unordered_map<int,list<Node>> freq_table; public: LFUCache(int capacity){ this->capacity = capacity; minfreq = 0; key_table.clear(); freq_table.clear(); } int get(int key){ if(capacity == 0) return -1; auto it = key_table.find(key); if(it == key_table.end()) return -1; list<Node>::iterator node = it->second; int val = node->val, freq = node->freq; freq_table[freq].erase(node); // 如果当前链表被删空了,在哈希表中删除,且更新minFreq; if(freq_table[freq].size() == 0){ freq_table.erase(freq); if(minfreq == freq) minfreq += 1; } // 插入到 freq+1中 freq_table[freq + 1].push_front(Node( key,val,freq+1)); key_table[key] = freq_table[freq +1].begin(); return val; } // put的时候,minfreq = 1 ,最新的数据使用频率一定是1 void put(int key, int val){ if(capacity == 0 ) return; auto it = key_table.find(key); if(it == key_table.end()){ if(key_table.size() == capacity){ auto it2 = freq_table[minfreq].back(); key_table.erase(it2.key); freq_table[minfreq].pop_back(); if(freq_table[minfreq].size() == 0){ freq_table.erase(minfreq); } } freq_table[1].push_front(Node(key,val,1)); key_table[key] = freq_table[1].begin(); minfreq = 1; }else{ // 与get基本一致,除了需要更新缓存的值。 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 += 1; } freq_table[freq + 1] .push_front(Node(key,val,freq+1)); key_table[key] = freq_table[freq + 1].begin(); } } };

参考

https://leetcode-cn.com/problems/lfu-cache/

点赞