LeetCode 460 LFU Cache

    
        标签：
        
            设计数据结构
        
            LeetCode
        
    发布于：2022-02-10 14:45:23
    编辑于：2022-02-10 17:45:15
    浏览量：911

概述

https://leetcode.com/problems/lfu-cache/

注意：

For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.

基于优先级队列的失败尝试

第一反应是用最小堆来维护 key 的访问频率。

如果给最小堆加入一个元素，该元素与顶层元素的值相同，其会取代它吗？不会：

最小堆：每个节点都小于等于它的子节点。

这种情况下顶部元素依然遵循定义，没必要僭越。

时间复杂度 OKay 么？优先级队列的插入和删除元素都是 O(logn)，n 为队列中元素个数。所以应该 Okay。

额，优先级队列没办法访问中间元素啊，我们没办法更新频率。

附上没办法继续写的代码：

class LFUCache {
public:
    int capacity;
    typedef pair<int, int> pi;  // <count, key>
    priority_queue<pi, vector<pi>, greater<pi>> keyQueue;
    unordered_map<int, int> cache;
    LFUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if (cache.count(key) == 0) return -1;
        promote(key);
        return cache[key];        
    }
    
    void put(int key, int value) {
        if (cache.count(key) == 0) {
            if (keyQueue.size() == capacity) {
                evict();
            }
            cache[key] = value;
            keyQueue.emplace({1, key});
        } else {
            cache[key] = value;
            promote(key);
        }
    }
    
    int promote(int key) {
        
    }
    
    int evict() {
        auto key = keyQueue.top().second;
        keyQueue.pop();
        cache[key].erase();
    }
};

基于 Map + 双向链表的实现

https://labuladong.gitee.io/algo/2/20/46/

用到的数据结构：

一个 map 用来存键与（值，频率）对；
一个 map 用来存频率与对应的键列表对，注意这里的列表是 LinkedHashSet；

或者：

一个 map 用来存键与（值，频率）对；
一个 map 用来存频率与对应的键列表对，注意这里的列表是普通的双向链表；
一个 map 用来存键与 List 迭代器对（使我们能常数时间内访问链表的任意节点）；

下面的实现 Runtime Error 了，因为 LeetCode 用 capacity 为 0 的参数偷袭了我 50 多行的代码。这样的测试用例好么？这不好，希望 LeetCode 不要再犯这样的小聪明啊。

class LFUCache {
public:
    int capacity;
    int minFreq;
    unordered_map<int, pair<int, int>> cache;  // key -> <value, freq>
    unordered_map<int, list<int>> freq2keyList;  // freq -> [key1, key2, ..., keyn]
    unordered_map<int, list<int>::iterator> pointer;  // key -> iterator
    LFUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if (cache.count(key) == 0) return -1;
        promote(key);
        return cache[key].first;        
    }
    
    void put(int key, int value) {
        if (cache.count(key) != 0) {
            cache[key].first = value;
            promote(key);
            return;
        }
        
        if (cache.size() == capacity) {
            evict();
        }
        
        minFreq = 1;
        cache[key] = {value, minFreq};
        freq2keyList[minFreq].push_front(key);
        pointer[key] = freq2keyList[minFreq].begin();
    }
    
    void promote(int key) {
        int oldFreq = cache[key].second ++ ;
        int newFreq = cache[key].second;
        freq2keyList[oldFreq].erase(pointer[key]);
        if (freq2keyList[oldFreq].empty()) {
            freq2keyList.erase(oldFreq);
            if (minFreq == oldFreq) minFreq = newFreq;
        }
        freq2keyList[newFreq].push_front(key);
        pointer[key] = freq2keyList[newFreq].begin();
    }
    
    void evict() {
        auto key = freq2keyList[minFreq].back();
        freq2keyList[minFreq].pop_back();
        if (freq2keyList[minFreq].empty()) {
            freq2keyList.erase(minFreq);
            // but this time we don't need to care minFreq anymore, cause after evict(), minFreq will be reset to 1
        }
        cache.erase(key);
        pointer.erase(key);
    }
};

在 put() 里加了一行 if (capacity == 0) return; 完事。

Links: leetcode-460-lfu-cache