LFU Cache

原題鏈接LFU Cache

實(shí)現(xiàn)LFU置換算法，置換規(guī)則是當(dāng)容量滿時(shí)換出使用頻率最少的那個(gè)，不考慮一定時(shí)間內(nèi)的頻率的情況下，可以采用每個(gè)頁使用的次數(shù)作為判斷依據(jù)，相當(dāng)于從創(chuàng)建之初到現(xiàn)在的使用頻率

類似的置換算法為了在效率上有一定的保障，通常都是空間換時(shí)間，本題也明確規(guī)定的時(shí)間復(fù)雜度是O(1)，而O(1)多數(shù)情況下都是類似map的存儲(chǔ)結(jié)構(gòu)，當(dāng)然，C++中map和set是采用紅黑樹實(shí)現(xiàn)的，效率是O(lgN)，而另一個(gè)采用hashtable實(shí)現(xiàn)的unordered_map和unordered_set則是O(1)的效率

接下來考慮采用map保存的數(shù)據(jù)

首先為了根據(jù)鍵key找到值value和它的使用頻率freq，可以考慮保存一個(gè)類似unordered_map<int, std::pair<int, int>>的結(jié)構(gòu)代表鍵到\<值，頻率>的映射。稱為keyToVF

接下來考慮當(dāng)容量滿時(shí)進(jìn)行置換的情況，為了讓效率進(jìn)一步提升，可以借鑒類似操作系統(tǒng)內(nèi)核處理不同狀態(tài)進(jìn)程控制塊時(shí)的策略，即每種狀態(tài)的進(jìn)程控制塊維護(hù)一個(gè)鏈表，這里就只需為每個(gè)頻率維護(hù)一個(gè)鏈表，再存儲(chǔ)在map中，即unordered_map<int, list<int>>結(jié)構(gòu)代表頻率freq到保存鍵的鏈表的映射。稱為fToList

但是這樣仍然不夠，沒有辦法確定某一時(shí)刻最小的頻率是多少，所以還需要使用一個(gè)變量記錄當(dāng)前最小使用頻率minF，當(dāng)置換時(shí)，直接從fToList[minF]中移除一個(gè)頁，這里可以事先規(guī)定，新加入的都添加到鏈表尾部，移除則移除頭部

當(dāng)調(diào)用get函數(shù)時(shí)需要對(duì)鍵key的頻率進(jìn)行增加，從keyToVF中可以找到key對(duì)應(yīng)的值和頻率，從fToList中可以找到頻率對(duì)應(yīng)的鏈表，需要做的事情是從這個(gè)鏈表中刪除key，然后添加到fToList[freq+1]這個(gè)鏈表中。由于鏈表刪除與key相等的節(jié)點(diǎn)時(shí)需要遍歷鏈表，而刪除指定迭代器處的節(jié)點(diǎn)時(shí)只需要改變幾個(gè)指針，所以為了更進(jìn)一步提高速度，再次使用一個(gè)map保存鍵key到key在鏈表中迭代器的映射即unordered_map<int, list<int>::iterator>。稱為keyToIt

至此三個(gè)map都已經(jīng)構(gòu)造完成，get和put的工作只是在線性時(shí)間操作不同的map而已

代碼如下

class LFUCache { public:LFUCache(int capacity) {capacity_ = capacity;size_ = 0;minF_ = 1;}int get(int key) {/* 不存在key */if(keyToVF_.find(key) == keyToVF_.end()) return -1;/* 將key從key的頻率map中刪除，然后加到freq+1的鏈表中 */fToList_[keyToVF_[key].second].erase(keyToIt_[key]);fToList_[++keyToVF_[key].second].push_back(key);keyToIt_[key] = --fToList_[keyToVF_[key].second].end();/* 更新最小頻率 */if(fToList_[minF_].empty())++minF_;return keyToVF_[key].first;}void put(int key, int value) {if(capacity_ == 0) return;/* 將頻率加一，返回非-1表示存在key，重新設(shè)置value即可 */if(get(key) != -1){keyToVF_[key].first = value;return;}if(size_ == capacity_){/* 刪除頻率最小的鏈表頭 */keyToVF_.erase(fToList_[minF_].front());keyToIt_.erase(fToList_[minF_].front());fToList_[minF_].pop_front();--size_;}/* 添加數(shù)據(jù)到頻率為1的鏈表中 */keyToVF_[key] = std::make_pair(value, 1);fToList_[1].push_back(key);keyToIt_[key] = --fToList_[1].end();minF_ = 1;++size_;} private:unordered_map<int, std::pair<int, int>> keyToVF_;unordered_map<int, list<int>::iterator> keyToIt_;unordered_map<int, list<int>> fToList_;int capacity_;int size_;int minF_; };/*** Your LFUCache object will be instantiated and called as such:* LFUCache obj = new LFUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/

今天才發(fā)現(xiàn)csdn的markdown的<>是敏感字符….

總結(jié)

以上是生活随笔為你收集整理的每天一道LeetCode-----实现LFU置换算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。