LRU 缓存

概述

LRU（Least Recently Used，最近最少使用）算法是地址转换旁路缓冲储存器（TLB）中数据的更新策略。TLB中存储的是虚拟地址到物理地址的映射，可以避免CPU多次在内存中查找页表来将虚拟地址转换为物理地址的时间开销。TLB的容量是有限的，所以在我们存入新的数据且TLB中没有空余容量时应当踢出一些数据。而LRU算法的思想是踢出TLB中上次使用距今最久远的数据，即最近最少使用的数据。

---

例题

LeetCode 146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存

• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

---

题解

因为要以 O(1) 的时间复杂度取得 key 对应的 value ，所以我们使用哈希表来储存数据。而要以 O(1) 的时间复杂度改变节点的数据，不难想到使用链表的数据结构。所以我们可以确认本题使用的数据结构是哈希表+链表，其中哈希表的键就是题目给的键，哈希表的值是我们自定义的Node类指针。

struct Node {
    int val;
    int key;
    Node* prev;
    Node* next;
    Node(int k, int v) :val(v), key(k), prev(nullptr), next(nullptr) {};
};
unordered_map<int, Node* > map;

当我们查询或修改某一个节点时，我们应该将他移到链表的末尾。这样越靠近链表末尾的节点最后一次访问的时间离现在越近。当链表中的节点数到达容量值时，我们踢出链表的头节点，并将头节点的后一个节点设置为新的头节点。

Node* curr = map[key];
if (now == 1) return curr->val;
if (curr == head) head = head->next;
if (curr == end) end = end->prev;
if (curr->prev) curr->prev->next = curr->next;
if (curr->next) curr->next->prev = curr->prev;
curr->prev = end;
curr->next = nullptr;
end->next = curr;
end = end->next

完整代码

class LRUCache {
private:
    int cap;
    int now;
    struct Node {
        int val;
        int key;
        Node* prev;
        Node* next;
        Node(int k, int v) :val(v), key(k), prev(nullptr), next(nullptr) {};
    };
    Node* head;
    Node* end;
    unordered_map<int, Node*> map;
public:
    LRUCache(int capacity) {
        this->cap = capacity;
        this->now = 0;
        head = new Node(0, 0);
        end = head;
    }

    int get(int key) {
        if (map.count(key) > 0) {
            Node* curr = map[key];
            if (now == 1) return curr->val;
            if (curr == head) head = head->next;
            if (curr == end) end = end->prev;
            if (curr->prev) curr->prev->next = curr->next;
            if (curr->next) curr->next->prev = curr->prev;
            curr->prev = end;
            curr->next = nullptr;
            end->next = curr;
            end = end->next;
            return curr->val;
        }
        return -1;
    }

    void put(int key, int value) {
        if (map.count(key) > 0) {
            Node* curr = map[key];
            if (now == 1) {
                curr->val = value;
                return;
            }
            if (curr == head) head = head->next;
            if (curr == end) end = end->prev;
            if (curr->prev) curr->prev->next = curr->next;
            if (curr->next) curr->next->prev = curr->prev;
            curr->prev = end;
            curr->next = nullptr;
            end->next = curr;
            end = end->next;
            curr->val = value;
        }
        else {
            Node* newnode = new Node(key, value);
            map[key] = newnode;
            now++;
            if (now == 1) {
                head = newnode;
                end = newnode;
                return;
            }
            end->next = newnode;
            newnode->prev = end;
            end = end->next;
            if (now > cap) {
                map.erase(head->key);
                head = head->next;
                head->prev = nullptr;
                now--;
            }
        }
        return;
    }
};

---

有的没的

今日最佳弔图

虽然我七选三没选物理，但是高三闲的没事的时候（正经人谁高三闲的没事啊）喜欢翻翻同桌的物理书，平时刷B站的时候也看过介绍相对论的视频，所以我能看懂这张图。太好玩儿了，哈哈！

开始学习操作系统了

上周一启动了操作系统的学习，学习资料是《操作系统导论》。今天是第九天，已经看了三百来页了，这应该是我大学以来有效阅读量最大的一段时间了吧。目前学到的知识可能还比较浅，有些地方囫囵吞枣地就过去了，以后还需要多多积累呀。这篇Blog也是在书上看到了LRU算法才想起来之前在LeetCode上好像写到过（后来发现写到过的应该是LFU，过两天也写成博客吧），才重新回去做了一遍写出来的。

没事听点歌（周杰伦 - 晴天）