C++實現(xiàn)支持泛型的LFU詳解
首先定義LFU存儲數(shù)據(jù)節(jié)點ListNode的結構, 此結構支持鍵K和值V的模板,為了在有序元素中實現(xiàn)比較(嚴格小于),這里需要重載小于號,如果此數(shù)據(jù)的使用頻次最少,則小于結果為true,如果頻次相等,輪次早的數(shù)據(jù)最小。
template<typename K, typename V> struct ListNode { K key; V value; int freq; long cur; bool operator<(const ListNode &x) const { if (freq < x.freq) return true; else if (freq == x.freq) return cur < x.cur; else return false; } };
然后我們來實現(xiàn)lfu類,我們用unordered_map去存key值對應的ListNode,用set<ListNode<K,V>> freq來充當頻次的存儲容器,使用set的好處是自動排序,頻次小的數(shù)據(jù)迭代器會被排到freq的begin(),刪除是只需要erase掉begin所指向的迭代器即可。我們來具體分析get和put操作
- get操作首先去map中查詢此key對應ListNode是否存在,如果此數(shù)據(jù)存在,將其對應的頻次+1(這里用reinsert函數(shù)實現(xiàn)),如果數(shù)據(jù)不存在,返回-1。
- put操作也要去map中查詢此key對應ListNode是否存在,若存在,直接將ListNode的value更新,并且將其對應的頻次+1(同上),否則,在map對應此鍵值的桶中插入ListNode,然后在freq中將其對應的頻次設為1并插入。
完整代碼如下:
#include <map> #include <set> #include <unordered_map> using namespace std; template<typename K, typename V> struct ListNode { K key; V value; int freq; long cur; bool operator<(const ListNode &x) const { if (freq < x.freq) return true; else if (freq == x.freq) return cur < x.cur; else return false; } }; template<typename K, typename V> class lfu { private: long cur_rount; int capacity; unordered_map<int, ListNode<K, V>> m; set<ListNode<K, V>> freq; public: lfu(int capacity) { capacity = capacity; cur_rount = 0; } V get(K key) { auto it = m.find(key); if (it == m.end()) return -1; V value = it->second.value; reinsert(it->second); return value; } void put(K key, V value) { if (capacity == 0) return; auto it = m.find(key); if (it != m.end()) { it->second.value = value; reinsert(it->second); return; } if (m.size() == capacity) { const ListNode<K, V> &node = *freq.begin(); m.erase(node.key); freq.erase(node); } ListNode<K, V> node{key, value, 1, ++cur_rount}; m[node.key] = node; freq.insert(node); } void reinsert(ListNode<K, V> &node) { freq.erase(node); ++node.freq; node.cur = ++cur_rount; freq.insert(node); } };
這里寫了一個簡單的主函數(shù)去驗證,K和V都使用int進行實例化。
可以看到第一次查詢,得到key=1的值為8,符合預期,在插入key=7 value=10的ListNode后,LFU頻次最低的Key=5 ListNode。此時再去get Key=5的值會得到一個-1,符合預期。
總結
本篇文章就到這里了,希望能夠給你帶來幫助,也希望您能夠多多關注腳本之家的更多內(nèi)容!
相關文章
VS2017開發(fā)C語言出現(xiàn)“no_init_all“的解決辦法
這篇文章介紹了VS2017開發(fā)C語言出現(xiàn)“no_init_all“的解決辦法,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-12-12c語言實現(xiàn)的貨物管理系統(tǒng)實例代碼(增加刪除 查找貨物信息等功能)
這篇文章主要介紹了c語言實現(xiàn)的貨物管理系統(tǒng),可增加刪除、查找貨物信息、顯示貨物信息、排序貨物銷量等操作,大家參考使用吧2013-11-11