LFU算法 初始频率 动态频率

    LFU（Least 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_map<int, list<pair<int, int>>::iterator>  m_Iter;  //链表索引list<pair<int, int>>                                m_List;  //(key,value) 链表public:LFUCache(int capacity){m_nCapacity = capacity;m_Iter.clear();m_List.clear();}int Get(int key){unordered_map<int, list<pair<int, int>>::iterator>::iterator iter = m_Iter.find(key);if (iter == m_Iter.end())return -1;UpdateNode(key, m_Iter[key]->second);pair<int,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));list<pair<int, 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_map<int, pair<int, int>>      m_map;      //(key,value,freq) 三元组unordered_map<int, list<int>>           m_freqList; //(freq,key)  频次链表unordered_map<int, list<int>::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);}};