快捷導(dǎo)航

C++ 實(shí)現(xiàn)LRU 與 LFU 的緩存算法

更新時(shí)間：2021年09月13日 11:11:31 作者：Ito Schum

設(shè)計(jì)和實(shí)現(xiàn)一個(gè)LRU 緩存機(jī)制。其支持獲取數(shù)據(jù) get 和寫入數(shù)據(jù) put，設(shè)計(jì)并實(shí)現(xiàn)最少訪問頻率（LFU）緩存的數(shù)據(jù)結(jié)構(gòu)。LFU的每個(gè)數(shù)據(jù)塊都有一個(gè)引用計(jì)數(shù)，所有數(shù)據(jù)塊按照引用計(jì)數(shù)排序，具有相同引用計(jì)數(shù)的數(shù)據(jù)塊則按照時(shí)間進(jìn)行排序。其支持get 和 put，具體了解請(qǐng)看下文

一、LRU (Least Recently Used) 緩存

詳見 LeetCode Q146

https:// leetcode.com/problems/l ru-cache/

https:// leetcode-cn.com/problem s/lru-cache/

問題描述：

LRUCache(int capacity) 以正整數(shù)作為容量 capacity 初始化 LRU 緩存
int get(int key) 如果關(guān)鍵字 key 存在于緩存中，則返回關(guān)鍵字的值，否則返回 -1 。
void put(int key, int value) 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值；如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字-值」。當(dāng)緩存容量達(dá)到上限時(shí)，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。
在 O(1) 時(shí)間復(fù)雜度內(nèi)完成這兩種操作

所用數(shù)據(jù)結(jié)構(gòu)：

為了使 get 與 put 操作的平均時(shí)間復(fù)雜度為 O(1) ，

使用雙向鏈表 (STL list ) 儲(chǔ)存緩存內(nèi)容 (使用 STL pair {key, value} 表示),
使用哈希表 (STL unordered_map ) 儲(chǔ)存 “key” 到 “pair iterator ” 的關(guān)系映射

typedef std::unordered_map<int, std::list<std::pair<int, int> >::iterator > CacheMap;
typedef std::list<std::pair<int, int> > LRUList;

流程圖：

get function

put function

代碼實(shí)現(xiàn)：

#include <iostream>
#include <list>
#include <unordered_map>

typedef std::unordered_map<int, std::list<std::pair<int, int> >::iterator > CacheMap;
typedef std::list<std::pair<int, int> > LRUList;

class LRUCache {
public:
    LRUCache(int capacity) {
        _capacity = capacity;
    }

    int get(int key) {
        CacheMap::iterator cache_itr = _cacheMap.find(key);
        if (cache_itr == _cacheMap.end() ) { 
            return -1; 
        }
        makeMostRecent(key, _cacheMap[key]->second);
        LRUList::iterator list_itr = _LRUList.end();
        --list_itr;
        return list_itr->second;
    }

    void put(int key, int value) {
        if (_cacheMap.find(key) != _cacheMap.end()) {
            makeMostRecent(key, value);
            return;
        }
        if (_LRUList.size() >= _capacity) {
            removeLeastRecentTask(key);
        }
        addMostRecentTask(key, value);
    }

private:
    void makeMostRecent(int key, int value) {
        _LRUList.erase(_cacheMap[key]);
        _LRUList.push_back(std::make_pair(key, value) );
        LRUList::iterator list_itr = _LRUList.end();
        _cacheMap[key] = --list_itr;
    }

    void removeLeastRecentTask(int key) {
        int keyToRemove = _LRUList.begin()->first;
        _LRUList.erase(_LRUList.begin());
        _cacheMap.erase(keyToRemove);
    }

    void addMostRecentTask(int key, int value) {
        _LRUList.push_back(std::make_pair(key, value) );
        LRUList::iterator list_itr = _LRUList.end();
        _cacheMap[key] = --list_itr;
    }

    int _capacity;
    LRUList _LRUList;
    CacheMap _cacheMap;
};

// n = item number of the LRU list, aka capacity
// Time: O(1)
// Space: O(n)

運(yùn)行測(cè)試：

Accepted
22/22 cases passed (412 ms)
Your runtime beats 69.45 % of cpp submissions
Your memory usage beats 48.08 % of cpp submissions (174 MB)

二、LFU (Least Frequently Used) 緩存

詳見 LeetCode Q460

https:// leetcode.com/problems/l fu-cache/

https:// leetcode-cn.com/problem s/lru-cache/

問題描述：

LFUCache(int capacity) - 用數(shù)據(jù)結(jié)構(gòu)的容量 capacity 初始化對(duì)象
int get(int key) - 如果鍵存在于緩存中，則獲取鍵的值，否則返回 -1 。
void put(int key, int value) - 如果鍵已存在，則變更其值；如果鍵不存在，請(qǐng)插入鍵值對(duì)。當(dāng)緩存達(dá)到其容量時(shí)，則應(yīng)該在插入新項(xiàng)之前，使最不經(jīng)常使用的項(xiàng)無效。在此問題中，當(dāng)存在平局（即兩個(gè)或更多個(gè)鍵具有相同使用頻率）時(shí)，應(yīng)該去除最近最久未使用的鍵。
「項(xiàng)的使用次數(shù)」就是自插入該項(xiàng)以來對(duì)其調(diào)用 get 和 put 函數(shù)的次數(shù)之和。使用次數(shù)會(huì)在對(duì)應(yīng)項(xiàng)被移除后置為 0 。
為了確定最不常使用的鍵，可以為緩存中的每個(gè)鍵維護(hù)一個(gè) 使用計(jì)數(shù)器。使用計(jì)數(shù)最小的鍵是最久未使用的鍵。
當(dāng)一個(gè)鍵首次插入到緩存中時(shí)，它的使用計(jì)數(shù)器被設(shè)置為 1 (由于 put 操作)。對(duì)緩存中的鍵執(zhí)行 get 或 put 操作，使用計(jì)數(shù)器的值將會(huì)遞增。

所用數(shù)據(jù)結(jié)構(gòu)：

為了使 get 與 put 操作的平均時(shí)間復(fù)雜度為 O(1) ，

使用哈希表 (STL unordered_map ) 儲(chǔ)存 “key” 到 “value 與 frequency” 的關(guān)系映射 (使用 STL pair {value, frequency} 表示)
使用哈希表 (STL unordered_map ) 儲(chǔ)存 “frequency” 到 “對(duì)應(yīng)所有的 key” 的關(guān)系映射 (key 使用雙向鏈表，即 STL list 存儲(chǔ))
使用哈希表 (STL unordered_map ) 儲(chǔ)存 “key” 到 “2 中存儲(chǔ) key 所用 list 中對(duì)應(yīng) iterator ” 的關(guān)系映射

std::unordered_map<int, std::pair<int, int> > _keyToValFreq;
std::unordered_map<int, std::list<int> > _freqToKeyList;
std::unordered_map<int, std::list<int>::iterator> _keyToKeyListItr;

流程圖：

get function

put function

代碼實(shí)現(xiàn)：

#include <iostream>
#include <list>
#include <unordered_map>

class LFUCache {
public:
    LFUCache(int capacity) {
        _capacity = capacity;
    }

    int get(int key) {
        // If key doesn't exist
        if (_keyToValFreq.find(key) == _keyToValFreq.end() ) {
            return -1;
        }
        // if key exists, increse frequency and reorder
        increaseFreq(key);
        return _keyToValFreq[key].first;
    }

    void put(int key, int value) {
        if (_capacity <= 0) { return; }
        // if key exists
        if (_keyToValFreq.find(key) != _keyToValFreq.end() ) {
            _keyToValFreq[key].first = value;
            increaseFreq(key);
            return;
        }
        // if key doesn't exist
        // if reached hashmap's max capacity, remove the LFU (LRU if tie)
        if (_keyToValFreq.size() >= _capacity) {
            int keyToRmove = _freqToKeyList[_minFreq].back();
            _freqToKeyList[_minFreq].pop_back();
            _keyToKeyListItr.erase(keyToRmove);
            _keyToValFreq.erase(keyToRmove);
        }
        // Then add new item with frequency = 1
        addNewTask(key, value);
    }

    void increaseFreq(int key) {
        // Update the freq in the pair
        int oldFreq = _keyToValFreq[key].second++;

        // Detele the old freq by itr
        _freqToKeyList[oldFreq].erase(_keyToKeyListItr[key]);
        // Add the new freq and re-assign the itr
        _freqToKeyList[oldFreq + 1].emplace_front(key);
        _keyToKeyListItr[key] = _freqToKeyList[oldFreq + 1].begin();

        // Update minFreq
        if (_freqToKeyList[_minFreq].empty() ) {
            _minFreq = oldFreq + 1;
        }
    }

    void addNewTask(int key, int value) {
        // Add new key-value/freq to all hashmaps
        _minFreq = 1;
        _keyToValFreq[key] = std::make_pair(value, _minFreq);
        _freqToKeyList[_minFreq].emplace_front(key);
        _keyToKeyListItr[key] = _freqToKeyList[_minFreq].begin();
    }

private:
    int _capacity;
    int _minFreq;
    std::unordered_map<int, std::pair<int, int> > _keyToValFreq;
    std::unordered_map<int, std::list<int> > _freqToKeyList;
    std::unordered_map<int, std::list<int>::iterator> _keyToKeyListItr;
};

// n = item number of the LFU, aka capacity
// Time: O(1)
// Space: O(n)

運(yùn)行測(cè)試：

Accepted
24/24 cases passed (464 ms)
Your runtime beats 72.37 % of cpp submissions
Your memory usage beats 45.99 % of cpp submissions (186.7 MB)

到此這篇關(guān)于C++ 實(shí)現(xiàn)LRU 與 LFU 的緩存算法的文章就介紹到這了,更多相關(guān)C++ 實(shí)現(xiàn)LRU 與 LFU 緩存算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: