首页 > 代码库 > LRU算法的设计
LRU算法的设计
一道LeetCode OJ上的题目，要求设计一个LRU（Least Recently Used）算法，题目描述如下：
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(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.
花了一个上午的时间来做这道题，终于Accepted了。感觉这道题出的非常好，做完这道题，对LRU算法的理解就不只局限在理论上了。LRU算法是一种cache置换算法，当cache容量不够时，将最久未使用的条目置换出去，换入新的当前需要使用的条目。
既然是设计题，那么首先就要确定数据结构。如何快速定位某条记录是否位于cache中，可以使用map，map的内部机制是一颗红黑树，时间复杂度为O(logn)，但是我使用了另一个结构——unordered_map，这个关联容器是C++11中新加入的，利用hash函数进行定位，时间复杂度为O(1)。将unordered_map初始化为unordered_map<key, value>，就能快速读写某个key对应的记录了。下面考虑如何实现LRU的相关算法。既然每次要淘汰最久未使用的记录，那么可以使用一个优先队列，队列开头存放最久未使用的记录，队列结尾存放最近刚刚被使用（读或写）过的记录。当需要换出记录时，选择优先队列开头的元素即可；当读、写完某条记录后，需要将该记录放到优先队列末尾，这里分两种情况：
- Cache中存在这条记录，则将记录移动到队列尾部。
- Cache中不存在这条记录，则将记录加入到队列尾部。
那么问题来了，用C++中的什么结构充当这个优先队列呢？STL中的queue和priority_queue肯定不行，因为这两个数据结构只有两端开放，无法遍历内部元素，这对于上面的情况1是不适用的。刚开始我想到了使用vector，使用完某个记录后就在vector中线性查找该记录，然后将它移动到vector末尾。这种操作的效率是O(n)，提交后系统出现了“Time Limit Exceeded”的错误，看来光有线性时间复杂度是不行的。后来想到了list，在list上移动一个节点只需要常数时间，我将list中的每一个节点关联到unordered_map的value成员上，也就是unordered_map<key, node*>。这样一来，查找某条记录、修改优先队列这两个操作都只需要常数时间。说起来有一点拗口，代码表达的意思更加直白，整个代码如下所示：
/* * https://oj.leetcode.com/problems/lru-cache/ */#include <iostream>#include <vector>#include <unordered_map>using namespace std;class Node {public: int key; int value; Node *prev; Node *next; Node(int k, int v) : key(k), value(v), prev(NULL), next(NULL) {}};class LinkList {public: int capacity; int size; Node *first; Node *last; LinkList(int c) : capacity(c), size(0) { first = new Node(0, 0); last = new Node(0, 0); first->next = last; last->prev = first; }};class LRUCache{public: LRUCache(int capacity) : PriorityLink(capacity) {} int get(int key) { if (mp.find(key) != mp.end()) { Node *pNode = mp[key]; if (pNode->next != PriorityLink.last) { unlink(pNode); link(pNode); } return pNode->value; } else return -1; } void set(int key, int value) { if (mp.find(key) != mp.end()) { Node *pNode = mp[key]; pNode->value =http://www.mamicode.com/ value; if (pNode->next != PriorityLink.last) { unlink(pNode); link(pNode); } } else { if (PriorityLink.size == PriorityLink.capacity) { // full Node *remove = PriorityLink.first->next; unlink(remove); mp.erase(remove->key); delete remove; } else PriorityLink.size++; Node *add = new Node(key, value); link(add); mp[key] = add; } } void link(Node *pNode) { // put node to back of PriorityLink pNode->prev = PriorityLink.last->prev; pNode->next = PriorityLink.last; PriorityLink.last->prev = pNode; pNode->prev->next = pNode; } void unlink(Node *pNode) { pNode->prev->next = pNode->next; pNode->next->prev = pNode->prev; pNode->prev = NULL; pNode->next = NULL; } LinkList PriorityLink; unordered_map<int, Node*> mp;};int main(){ LRUCache mem(2); mem.set(2, 1); mem.set(3, 2); cout << mem.get(3); cout << mem.get(2); mem.set(4, 3); //mem.set(4, 1); cout << mem.get(2); cout << mem.get(3); cout << mem.get(4); system("pause"); return 0;}
LRU算法的设计