NC94 LFU缓存结构设计

题目描述

一个缓存结构需要实现如下功能。

• set(key, value)：将记录(key, value)插入该结构
• get(key)：返回key对应的value值, 但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；如果调用次数最少的key有多个，上次调用发生最早的key被删除

这就是LFU缓存替换算法。实现这个结构，K作为参数给出

1. 哈希表+平衡树

方法一用到的是平衡二叉树， 在c++中可以使用stl的set，Java中可以使用TreeSet,其底层都是红黑树。（什么，你是py选手？手撕吧）本文以C++为例叙述下面的解决方法。

1.1 定义数据结构

因为这里不光有k，v，还要维护进入的时间（版本号）和频率，因此我们需要这样定义每个kv组，称为节点Node：

struct Node {
    int freq; // 频率
    int time; // 插入时间
    int key, value;

    // 重载比较方法，以频率为第一关键字，插入时间为第二关键字
    bool operator< (const Node& p) const {
        return p.freq == freq ? time < p.time : freq < p.freq;
    }
}

这里，我们需要两个数据结构，一个是哈希表key_map，用来维护每个key对应的节点，一个是平衡树rb_tree维护node的顺序。 最后还需要记录下容量和时间戳。

unordered_map<int, Node> key_map;
set<Node> rb_tree;
int capacity, timestamp;

1.2 get、set操作

对于get操作，我们先从key_map里找到对应的节点，再c从rb_tree中取出并删掉，更新它的time和freq再放回去。

对于set操作，我们从key_map里找到对应的节点，如果有，则跟get差不太多，区别是需要更新value,如果没有，则插入缓存，这时候需要看整个cache是不是满了，如果满了，则进入淘汰策略。

淘汰策略，根据题意就是，最近最少使用的，其实按我们的Node的排序方案，就等价于平衡树里最小的节点，我们去掉这个点就好了。

class Solution {
public:
    /**
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        init_lfu(k);
        
        vector<int> res;
        
        for (auto vec : operators) {
            int opt = vec[0], x, y;
            if (opt == 1) {
                x = vec[1], y = vec[2];
                set(x, y);
            } else if (opt == 2) {
                x = vec[1];
                res.push_back(get(x));
            }
        }
        return res;
    }
private:
    typedef struct Node{
        int freq; // 频率
        int time; // 插入时间
        int key, value;

        // 重载比较方法，以频率为第一关键字，插入时间为第二关键字
        bool operator< (const Node& p) const {
            return p.freq == freq ? time < p.time : freq < p.freq;
        }
    } Node;
    
    unordered_map<int, Node> key_map;
    set<Node> rb_tree;
    int capacity, timestamp;
    
    void init_lfu(int _capacity) {
        capacity = _capacity;
        timestamp = 1;
    }
    
    int get(int key) {
        auto val_iterator = key_map.find(key);
        
        // 如果没有
        if (val_iterator == key_map.end()) return -1;
        
        Node node = val_iterator->second;
        
        rb_tree.erase(node);
        node.freq++;
        node.time = timestamp++;
        
        rb_tree.insert(node);
        key_map[node.key] = node;
        return node.value;
    }
    
    void set(int key, int val) {        
        auto val_iterator = key_map.find(key);
        
        // 没有
        if (val_iterator == key_map.end()) {
            // 缓存满
            if (key_map.size() == capacity) {
                // 淘汰
                auto temp = rb_tree.begin();
                // 这里的temp是迭代器
                key_map.erase(temp->key);
                rb_tree.erase(temp);
            }
            
            // 创建新Node
            Node new_node{1, timestamp++, key, val};
            // 装进两个结构
            rb_tree.insert(new_node);
            key_map[key] = new_node;
        } else {
            // 有，取出来，更新，再装回去
            Node node = val_iterator->second;
            
            rb_tree.erase(node);
            node.freq++;
            node.time = timestamp++;
            node.value = val;
            
            key_map[node.key] = node;
            rb_tree.insert(node);
        }
    }
};

• 时间复杂度: $O\left(qlogn\right)O(qlogn)$O(qlogn), 假设有$qq$q次操作，每次操作都只涉及平衡树的增删，平衡树的复杂度均为$O\left(logn\right)O(logn)$O(logn).哈希表可近似看做$O\left(1\right)O(1)$O(1)
• 空间复杂度: $O\left(K\right)O(K)$O(K). 整个结构的最大容量为K。

2. 两个哈希表

本题还可以有一种O(1)的方法，是在论文An O(1) algorithm for implementing the LFU cache eviction scheme中介绍的。

Node跟思路一接近，但是不需要time，也不需要比较，我们再定义两个哈希表。哈希表的value是双端链表，在c++中用list

unordered_map<int, list<Node>::iterator> key_map;
unordered_map<int, list<Node>> freq_map;
int min_freq, capacity;

其中freq_map维护每个频率下，节点的双端链表，key_map维护每个key对应的节点在freq_map中位置的迭代器。

对于get操作，我们先在key_map找到这个key在freq_map的地址，如果找到了，则把它从freq_map的freq这条链表删掉，再装到freq+1这条链表的头部，加到头部的原因是保证时间有序。

对于set操作，如果找到了，跟思路1和思路2的get操作差不多。如果没有，需要删除。

删除操作我们由于维护了min_freq，就可以找到去哪条链表里面删除，而且我们知道每条链表都是根据时间戳有序的，故删掉链表尾部即可。

对于新增操作，我们同时更新min_freq=1。

class Solution {
public:
    /**
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        init_lfu(k);
        
        vector<int> res;
        
        for (auto vec : operators) {
            int opt = vec[0], x, y;
            if (opt == 1) {
                x = vec[1], y = vec[2];
                set(x, y);
            } else if (opt == 2) {
                x = vec[1];
                res.push_back(get(x));
            }
        }
        return res;
    }
private:
    typedef struct Node{
        int freq; // 频率
        int key, value;
    } Node;
    
    unordered_map<int, list<Node>::iterator> key_map;
    unordered_map<int, list<Node>> freq_map;
    int min_freq, capacity;
    
    void init_lfu(int _capacity) {
        capacity = _capacity;
        min_freq = 0;
    }
    
    int get(int key) {
        auto val_iterator = key_map.find(key);
        
        // 如果没有
        if (val_iterator == key_map.end()) return -1;
        
        auto node = val_iterator->second;
        
        int val = node->value, freq = node->freq;
        
        freq_map[freq].erase(node);
        
        if (freq_map[freq].size() == 0) {
            freq_map.erase(freq);
            if (min_freq == freq)
                min_freq++;
        }
        
        freq_map[freq+1].push_front(Node{freq+1, key, val});
        key_map[key] = freq_map[freq+1].begin();
        return val;
    }
    
    void set(int key, int val) {        
        auto val_iterator = key_map.find(key);
        
        // 没有
        if (val_iterator == key_map.end()) {
            // 缓存满
            if (key_map.size() == capacity) {
                // 拿min_freq那条链表的最后一个节点
                auto min_freq_last_node_iterator = freq_map[min_freq].back();
                
                key_map.erase(min_freq_last_node_iterator.key);
                
                freq_map[min_freq].pop_back();
                
                if (freq_map[min_freq].size() == 0)
                    freq_map.erase(min_freq);
            }
            
            Node node = Node{1, key, val};
            freq_map[1].push_front(node);
            key_map[key] = freq_map[1].begin();
            min_freq = 1;
        } else {
            // 有，取出来，更新，再装回去
            auto node_iterator = val_iterator->second;
               
            int freq = node_iterator->freq;
            freq_map[freq].erase(node_iterator);
            
            if (freq_map[freq].size() == 0) {
                freq_map.erase(freq);
                if (min_freq == freq)
                    min_freq++;
            }
            
            freq_map[freq+1].push_front(Node{freq+1, key, val});
            key_map[key] = freq_map[freq+1].begin();
        }
    }
};

• 时间复杂度: $O\left(q\right)O(q)$O(q), 假设有$qq$q次操作，每次操作都只涉及哈希表和链表操作，可近似为$O\left(1\right)O(1)$O(1)。
• 空间复杂度: $O\left(K\right)O(K)$O(K). 整个结构的最大容量为K。