leetcode: LRU 缓存
LRU 全称为 Least Recently Used,最近最少使用,常常用于缓存机制,比如 cpu 的 cache 缓存,使用了 LRU 算法。LRU 用于缓存机制时,关键的是当缓存满的时候有新数据需要加载到缓存的,这个时候需要淘汰谁的问题。
如下图所示,表示 LRU 算法的过程。假如有一个缓存,共有 4 个存储空间,按访问时间进行排序,最左边的存储空间存储的是最近访问的数据,最右边的存储空间存储的是最长时间没有访问的数据。
(1)一开始,缓存是空的,这个时候向缓存中放入一个数据 100,100 放到最左边的存储空间
(2)向缓存中放入一个数据 50,此时缓存有空余空间,所以将已有的数据向后移动,将 50 放到缓存的最左边
(3)向缓存中放入数据 500, 步骤与上一步相同
(4)向缓存中放入数据 1000,步骤与上一步相同
(5)读取数据 100,读取之后 100 就是最后访问的数据了,所以将 100 移到缓存的最左边,其它数据依次向后移动
(6)向缓存中放入数据 1,此时缓存是满的,所以需要先淘汰一个数据,从访问时间来看,最后一次访问 50 的间隔时间最长,也就是排在最右边的数据,所以将 50 淘汰,其它数据向后移动,将新数据 1 放入最左边的位置
如下是题目描述,题目的最后要求 get() 和 put() 的时间复杂度都要是 O(1) 的。使用数组来表示缓存难以满足 O(1) 的要求,因为在 put 或者 get 的时候,会引起数组数据的移动,数组中数据的移动时间复杂度是 O(n) 的。所以需要使用链表来表示缓存,当访问一个数据的时候需要将当前这个数据从原来的位置上删除,然后加到链表的头部,删除一个节点的话,需要将这个节点的前一个节点和下一个节点连接起来,如果使用单向链表的话,那么只能找到这个节点的下一个节点,找不到上一个节点,所以需要使用双向链表。
(1)使用双向循环链表来表示缓存
(2)为了满足时间复杂度是 O(1) 的要求,使用 data_addr_ 数组来保存节点的地址,数组的下标是 key,题目中说明了 key 的取值范围是 [0, 10000],所以可以使用一个数组来表示。使用 map 也不能保证时间复杂度是 O(1) 的,map 一般使用红黑树来实现,时间复杂度是 O(logn) 的。把数组的下标当 key,数组元素的值就是值,数组本省也可以当做一个简单的 map 来使用。
(3)当 put 数据时,要进行判断现在缓存是不是满了,如果满的话需要删除最久没有访问的数据,head_->next 保存最新访问的数据,head_->prev 保存最久没有访问的数据
struct Node {int key;int value;struct Node *next;struct Node *prev;
};class LRUCache {
public:LRUCache(int capacity) {capacity_ = capacity;head_ = new Node();head_->next = head_;head_->prev = head_;}int get(int key) {Node *node = data_addr_[key];if (node == nullptr) {return -1;}ListUnLink(node);ListLinkHead(node);return node->value;}void put(int key, int value) {if (data_addr_[key] != nullptr) { Node *node = data_addr_[key];ListUnLink(node);node->value = value;ListLinkHead(node);} else {Node *new_node = new Node();new_node->key = key;new_node->value = value;new_node->next = nullptr;new_node->prev = nullptr;if (count_ == capacity_) {Node *to_delete = head_->prev;ListUnLink(to_delete);data_addr_[to_delete->key] = nullptr;delete to_delete;count_--;}ListLinkHead(new_node);data_addr_[key] = new_node;count_++;}}void ListLinkHead(struct Node *ele) {ele->next = head_->next;ele->next->prev = ele;head_->next = ele;ele->prev = head_;}void ListUnLink(struct Node *ele) {ele->prev->next = ele->next;ele->next->prev = ele->prev;}private:int capacity_ = 0;int count_ = 0;Node *data_addr_[10001] = {nullptr};struct Node *head_ = nullptr;};