C++ 实现LRU 与 LFU 的缓存算法

算法描述

LRU和LFU是常用的缓存算法。它们能够优化系统读写速度，提高系统效率。

LRU

LRU (Least Recent Used)是最近最少使用算法，维护一个缓存队列，每次访问缓存中的一个元素时，将其移动到队列的头部，当缓存队列满时删除队尾元素，保证最近使用过的元素在缓存队列的最前面，最近没有使用过的元素在缓存队列的最后面。

LFU

LFU (Least Frequently Used)是利用元素访问次数的算法，维护一个缓存队列，每次访问缓存中的一个元素时，将该元素的访问次数增加1。当缓存队列满时，删除访问次数最少的元素。这种算法可以有效地处理热点数据的缓存问题。

算法实现

下面分别实现LRU和LFU算法。

LRU

使用哈希表和双向链表实现LRU算法，哈希表维护元素在链表中的位置，双向链表维护元素的访问顺序。

class Node { // 链表节点
public:
    int key, val;
    Node* prev;
    Node* next;
    Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
};

class LRUCache {
public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        if (!hash.count(key)) return -1; // 未找到元素
        Node* node = hash[key]; // 取出节点
        update(node); // 更新节点访问顺序
        return node->val;
    }

    void put(int key, int value) {
        if (hash.count(key)) {
            Node* node = hash[key]; // 取出节点
            node->val = value; // 更新节点
            update(node); // 更新节点访问顺序
        }
        else {
            if (list.size() == cap) { // 缓存队列已满
                Node* node = list.back(); // 取出队尾节点
                hash.erase(node->key); // 从哈希表中删除
                list.pop_back(); // 从链表中删除
                delete node; // 释放节点
            }
            Node* node = new Node(key, value); // 创建新节点
            list.push_front(node); // 新节点插入到队头
            hash[key] = node; // 将新节点加入哈希表
        }
    }

private:
    int cap; // 缓存容量大小
    list<Node*> list; // 双向链表，维护元素访问顺序
    unordered_map<int, Node*> hash; // 哈希表，记录元素在链表中的位置

    // 更新节点访问顺序
    void update(Node* node) {
        list.erase(node); // 先将节点从链表中删除
        list.push_front(node); // 将节点插入到队头
    }
};

LFU

使用哈希表、桶和两个双向链表实现LFU算法，哈希表维护元素在桶中的位置，每个桶记录访问次数相同的元素，一个双向链表维护桶的访问顺序，另一个双向链表维护元素的访问顺序。

class Node { // 链表节点
public:
    int key, val, freq;
    Node* prev;
    Node* next;
    Node(int k, int v, int f) : key(k), val(v), freq(f), prev(nullptr), next(nullptr) {}
};

class LFUCache {
public:
    LFUCache(int capacity) : cap(capacity), minFreq(0) {}

    int get(int key) {
        if (!hash.count(key)) return -1; // 未找到元素
        Node* node = hash[key]; // 取出节点
        update(node); // 更新节点访问顺序
        return node->val;
    }

    void put(int key, int value) {
        if (cap == 0) return;
        if (hash.count(key)) {
            Node* node = hash[key]; // 取出节点
            node->val = value; // 更新节点
            update(node); // 更新节点访问顺序
        }
        else {
            if (hash.size() == cap) { // 缓存队列已满
                DLList& list = freq[listHead->next->freq]; // 取出访问频率最小的桶
                Node* node = list.removeTail(); // 取出队尾节点
                hash.erase(node->key); // 从哈希表中删除
                delete node; // 释放节点
            }
            Node* node = new Node(key, value, 1); // 创建新节点
            freq[1].addHead(node); // 将新节点插入到访问频率为1的桶的头部
            hash[key] = node; // 将新节点加入哈希表
            listHead = &freq[1]; // 更新访问频率最小的桶
        }
    }

private:
    int cap; // 缓存容量大小
    int minFreq; // 最小访问频率
    DLList* listHead; // 访问频率最小的桶
    unordered_map<int, Node*> hash; // 哈希表，记录元素在桶中的位置
    unordered_map<int, DLList> freq; // 桶，记录访问频率相同的元素

    class DLList { // 双向链表
    public:
        DLList() : head(new Node(0, 0, 0)), tail(new Node(0, 0, 0)), size(0) { // 头尾哨兵节点
            head->next = tail;
            tail->prev = head;
        }

        void addHead(Node* node) { // 在头部添加节点
            node->next = head->next;
            node->prev = head;
            head->next->prev = node;
            head->next = node;
            ++size;
        }

        Node* removeTail() { // 删除尾部节点
            if (size == 0) return nullptr;
            Node* node = tail->prev;
            remove(node);
            return node;
        }

        void remove(Node* node) { // 删除指定节点
            node->prev->next = node->next;
            node->next->prev = node->prev;
            --size;
        }

        bool empty() const { return head->next == tail; }

    private:
        Node* head; // 头哨兵节点
        Node* tail; // 尾哨兵节点
        size_t size; // 链表长度
    };

    // 更新节点访问顺序
    void update(Node* node) {
        DLList& list = freq[node->freq]; // 取出节点所在的桶
        list.remove(node); // 从当前桶中删除节点
        if (list.empty() && node->freq == minFreq) { // 当前桶为空且节点所在桶是访问频率最小的桶
            ++minFreq; // 最小访问频率加1
            listHead = &freq[minFreq]; // 更新访问频率最小的桶
        }
        ++node->freq; // 节点访问频率加1
        freq[node->freq].addHead(node); // 将节点加入新桶的头部
    }
};

示例说明

下面给出两个示例说明。

示例1

LRUCache lruCache(2);
lruCache.put(1, 1);
lruCache.put(2, 2);
assert(lruCache.get(1) == 1); // 返回 1
lruCache.put(3, 3); // 缓存容量已满，需要删除最近最少使用的元素 2
assert(lruCache.get(2) == -1); // 返回 -1，因为元素 2 已经被删除
lruCache.put(4, 4); // 缓存容量已满，需要删除最近最少使用的元素 1
assert(lruCache.get(1) == -1); // 返回 -1，因为元素 1 已经被删除
assert(lruCache.get(3) == 3); // 返回 3
assert(lruCache.get(4) == 4); // 返回 4

示例2

LFUCache lfuCache(2);
lfuCache.put(1, 1);
lfuCache.put(2, 2);
assert(lfuCache.get(1) == 1); // 返回 1
lfuCache.put(3, 3); // 缓存容量已满，需要删除访问频率最小的元素 2
assert(lfuCache.get(2) == -1); // 返回 -1，因为元素 2 已经被删除
assert(lfuCache.get(3) == 3); // 返回 3
lfuCache.put(4, 4); // 缓存容量已满，需要删除访问频率最小的元素 1
assert(lfuCache.get(1) == -1); // 返回 -1，因为元素 1 已经被删除
assert(lfuCache.get(3) == 3); // 返回 3
assert(lfuCache.get(4) == 4); // 返回 4
lfuCache.put(3, 33); // 更新元素 3 的值，访问频率加1
assert(lfuCache.get(3) == 33); // 返回 33
assert(lfuCache.get(4) == 4); // 返回 4
lfuCache.put(2, 22); // 更新元素 2 的值，访问频率加1
assert(lfuCache.get(2) == 22); // 返回 22

以上就是C++实现LRU与LFU的缓存算法的完整攻略。