LeetCode LRU Cache

LeetCode LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

实现一个LUR cache。

我们知道数据的访问都有时间局部性和空间局部性,所以为了加快访问速度,把经常访问的数据放到高速缓存cache中,这样先查cache,不命中再查内存或者外存。

但是cache一般都很小,当新数据需要插入cache时,如果cache满,则需要替换掉cache中旧的元素。此时替换哪个元素就有很多策略了,可以把最久没访问的替换出去,也可以把访问频率最低的替换出去,还可以把最先进入的替换出去等等,各种策略就形成了不同的缓存替换算法。

LRU的意思是Least Recently Used (LRU),即把最近最久没访问的元素替换出去,是指时间上最久没访问的,而不是频率上访问最少的哦。

题目要求实现LRU的两个接口,分别是

  1. get(key),从LRU中获取key对应的value,如果LRU中不存在key,则返回-1
  2. put(key,value),把key和对应的value插入到LRU中,如果LRU满,则要替换掉最近最久没访问的元素

要求这两个操作都在O(1)时间内完成。

我们来分析一下应该用哪些数据结构使这两个操作都在O(1)时间内完成。首先get需要在O(1)时间内判断key是否在LRU中,所以可能需要用hash来存储<key,value>对。其次,需要缓存替换时,要在O(1)时间内把最久没访问的<key,value>删掉,同时插入新的<key,value>,删除和插入能在O(1)时间内完成的就是链表了。

综合上面的分析,我们可以用unordered_map+list来实现LRU,STL的list是一个双向链表。

参考这份代码。我们使用list<int> used来保存当前在LRU中的那些key,注意是key;用unordered_map<int, pair<int, list<int>::iterator>> cache来保存真实的缓存,cache的key就是LRU中现存的key,value是一个pair,保存了key对应的value,以及这个key在链表中的迭代器(指针)。两个操作的实现如下:

put(key,value)。每当有新<key,value>进入时,如果key已经在cache中,则只需要更新key对应的value,同时,刚访问的元素下次很可能再次访问,所以需要把这个key提到链表的表头(为了不让这个key沉到表尾)。如果key不在cache中,但cache已满,则需要把链表尾部的key对应的数据在cache中删掉,同时也需要在链表中删掉这个尾节点;如果cache不满,则把新key插入到链表表头,同时把<key,value>插入到cache中,且key在链表中的位置是list.begin()。

get(key)。如果key不在cache中,直接返回-1。如果key在cache中,直接从cache中得到对应的value,同时根据迭代器,把key提到链表表头。

根据上述算法描述,我们需要抽象一个函数,moveToHead(list<int>::iterator &it),即把迭代器it指向的那个key移到表头,包括两个操作,把it从it位置删掉,把it的值插到表头。

完整代码如下:

class LRUCache {
private:
	
	unordered_map<int, pair<int, list<int>::iterator>> cache;
	list<int> used;
	int _capacity;
	
	// 把it节点**剪切**到表头
	void moveToHead(list<int>::iterator &it) {
		int key = *it;
		used.erase(it);
		used.push_front(key);
		cache[key].second = used.begin();
	}
	
	
public:
	LRUCache(int capacity):_capacity(capacity) {

	}

	int get(int key) {
		if (cache.find(key) == cache.end())return -1;
		int value = cache[key].first;
		moveToHead(cache[key].second);
		return value;
	}

	void put(int key, int value) {
		if (cache.find(key) != cache.end()) {
			cache[key].first = value;
			moveToHead(cache[key].second);
		}
		else {
			if (used.size() == _capacity) {
				cache.erase(used.back());
				used.pop_back();
			}
			used.push_front(key);
			cache[key] = { value,used.begin() };
		}
	}
};

本代码提交AC,用时96MS。

我们还可以自己实现list,就是一个双向链表。这个双向链表包括头结点head和尾节点tail。为了插入删除的方便,我们设置了一个用不到的head和tail,所以真正的数据其实是在head和tail之间的,如下,节点1~3才是真正的数据节点

头 --> 节 --> 节 --> 节 --> 尾
节     点     点     点     节
点 <-- 1  <-- 2 <-- 3  <-- 点

这里我们抽象出了3个函数,removeFromList和moveToHead完成上一种实现中的moveToHead功能,即先把节点从原链表中删除(相当于摘下来),然后把这个节点安放到表头(上图节点1)。removeTail就是在需要替换时,删除表尾节点(上图节点3)。

完整代码如下:

class LRUCache {
private:
	struct Node {
		int key, value;
		Node *pre, *next;
		Node(int k, int v) :key(k), value(v), pre(NULL), next(NULL) {};
	};

	unordered_map<int, Node*> cache;
	Node *head, *tail;
	int _capacity;

	// 从原链表中删除节点node(摘下)
	void removeFromList(Node *node) {
		node->pre->next = node->next;
		node->next->pre = node->pre;
	}

	// 把节点node放到“表头”(安放)
	void moveToHead(Node *node) {
		node->next = head->next;
		head->next->pre = node;
		node->pre = head;
		head->next = node;
	}

	// 删除“尾节点”
	void removeTail() {
		Node *target = tail->pre;
		target->pre->next = target->next;
		target->next->pre = target->pre;
		delete target;
	}

public:
	LRUCache(int capacity) :_capacity(capacity) {
		head = new Node(0, 0); // 辅助头结点
		tail = new Node(0, 0); // 辅助尾节点
		head->next = tail;
		tail->pre = head;
	}

	int get(int key) {
		if (cache.find(key) == cache.end())return -1;
		int value = cache[key]->value;
		removeFromList(cache[key]);
		moveToHead(cache[key]);
		return value;
	}

	void put(int key, int value) {
		if (cache.find(key) != cache.end()) {
			cache[key]->value = value;
			removeFromList(cache[key]);
			moveToHead(cache[key]);
		}
		else {
			if (cache.size() == _capacity) {
				cache.erase(tail->pre->key);
				removeTail();
			}
			Node *node = new Node(key, value);
			cache[key] = node;
			moveToHead(node);
		}
	}
};

本代码提交AC,用时98MS。

Leave a Reply

Your email address will not be published. Required fields are marked *