珠海品牌机械网站建设,网站在建设中 英语,网站建设 图纸网,陕西住房城乡住房建设厅网站LFU#xff08;Least Frequently Used#xff09;算法是一种缓存淘汰策略#xff0c;其核心思想是根据数据的访问频率来决定淘汰哪些数据。具体来说#xff0c; LFU算法认为如果一个数据在过去一段时间内被访问的次数很少#xff0c;那么它在未来被再次访问的概率也… LFULeast Frequently Used算法是一种缓存淘汰策略其核心思想是根据数据的访问频率来决定淘汰哪些数据。具体来说 LFU算法认为如果一个数据在过去一段时间内被访问的次数很少那么它在未来被再次访问的概率也很低。因此当缓存空间不足时LFU算法会选择访问频率最低的数据进行淘汰。 在C中实现LFU算法通常需要以下几个步骤 数据结构设计LFU算法通常需要一个哈希表和一个优先队列。哈希表用于存储每个元素的访问计数键是元素的标识值是元素的访问次数。优先队列用于根据访问次数对元素进行排序以便快速找到访问次数最少的元素。 初始化在初始化时需要设置缓存的容量并创建一个哈希表和一个优先队列来存储数据和访问计数。 获取数据当调用get方法时如果键存在于缓存中则返回键的值并增加该键的访问计数。如果键不存在则返回-1。 插入数据当调用put方法时如果键已存在则更新其值并增加访问计数如果键不存在则插入新键值对并检查缓存是否已满。如果已满则淘汰访问次数最少的元素。 淘汰策略在淘汰元素时LFU算法会选择访问次数最少的元素。如果有多个元素具有相同的最小访问次数则选择最早插入的那个元素进行淘汰。
1 基于初始的频率
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存。int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 - 1。void put(int key, int value) 如果关键字已经存在则变更其数据值如果关键字不存在则插入该组「关键字 - 值」。当缓存容量达到上限时它应该在写入新数据之前删除最久未使用的数据值从而为新的数据值留出空间。在 O(1) 时间复杂度内完成这两种操作。 C写的伪代码如下
class LFUCache {
private:int m_nCapacity; //缓存的容量unordered_mapint, listpairint, int::iterator m_Iter; //链表索引listpairint, int m_List; //(key,value) 链表public:LFUCache(int capacity){m_nCapacity capacity;m_Iter.clear();m_List.clear();}int Get(int key){unordered_mapint, listpairint, int::iterator::iterator iter m_Iter.find(key);if (iter m_Iter.end())return -1;UpdateNode(key, m_Iter[key]-second);pairint,int tail m_List.back();return tail.second;}void Put(int key, int value){if (m_Iter.find(key) ! m_Iter.end()){UpdateNode(key, value);return;}//若容量已满则移除最近最少使用的节点if (m_List.size() m_nCapacity){DelLeastNode(key);}AddNode(key,value);}private:void UpdateNode(int key, int value){m_List.erase(m_Iter[key]); //删除原有的pairAddNode(key, value);}void AddNode(int key, int value){m_List.push_back(make_pair(key, value));listpairint, int::iterator iter m_List.end();m_Iter[key] --iter;}void DelLeastNode(int key){int id m_List.begin()-first;m_List.erase(m_List.begin());m_Iter.erase(id);}};2 基于动态的频率
每读一次该项的热度加1每写一次该项的热点也加1 LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象。 int get(int key) - 如果键存在于缓存中则获取键的值否则返回 - 1。 void put(int key, int value) - 如果键已存在则变更其值如果键不存在请插入键值对。当缓存达到其容量时 则应该在插入新项之前使最不经常使用的项无效。在此问题中当存在平局即两个或更多个键具有相同使用频率时 应该去除 最近最久未使用的键。 「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。 为了确定最不常使用的键可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。 当一个键首次插入到缓存中时它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作使用计数器的值将会递增。 C写的伪代码如下
class LFUCache {
private:int m_nCapacity; //容量int m_nMinFreq; //最小的使用次数unordered_mapint, pairint, int m_map; //(key,value,freq) 三元组unordered_mapint, listint m_freqList; //(freq,key) 频次链表unordered_mapint, listint::iterator m_lisIter; //(freq,index) 频次索引器LFUCache(int capacity){m_nCapacity capacity;m_nMinFreq 0;m_map.clear();m_freqList.clear();m_lisIter.clear();}void IncreaseFreq(int key){int oldFreq m_map[key].second;//在链表里删除旧元素m_freqList[oldFreq].erase(m_lisIter[key]);//添加元素并更新次数m_freqList[oldFreq 1].emplace_front(key); //从双端队列的头部加入元素m_lisIter[key] m_freqList[oldFreq 1].begin();if (m_freqList[m_nMinFreq].empty()){m_nMinFreq oldFreq 1;}}void AddNode(int key, int value){m_nMinFreq 1;m_map[key] make_pair(value, m_nMinFreq);m_freqList[m_nMinFreq].emplace_front(key);m_lisIter[key] m_freqList[m_nMinFreq].begin();}int Get(int key){if (m_map.find(key) m_map.end())return -1;IncreaseFreq(key);return m_map[key].first;}void Put(int key, int value){if (m_nCapacity 0)return;//若key存在则更新value值if (m_map.find(key) ! m_map.end()){m_map[key].first value;IncreaseFreq(key);return;}//处理容量已满的情况if (m_map.size() m_nCapacity){int id m_freqList[m_nMinFreq].back();m_freqList[m_nMinFreq].pop_back(); //弹出末尾的元素m_lisIter.erase(id); //删除该元素的索引m_map.erase(id); //删除该元素}//若key不存在则新建AddNode(key, value);}};
