Least Recently Used Algorithm

LRU（_Least Recently Used）_算法是操作系统中的一种页面置换（在缓存系统中也会用到），思想就是：每次都把最近最少使用的那个页面置换出去，这个思想基于，当前使用的页面在不久的将来也会使用。

比如在内存为 3 的情况下，依次请求如下页面2，3，4，2，1，3，7，5，4，3.那么内存中保存的依次保存的页面会变成如下所示（每一行表示当前页面请求之后，内存中的页面情况，左边的页面比右边页面旧（也就是最后一次访问的时间早），这里有一个动态视频，给出每一次的情况（需要翻墙）

  1. 2
  2. 2 3
  3. 2 3 4
  4. 3 4 2
  5. 4 2 1
  6. 2 1 3
  7. 1 3 7
  8. 3 7 5
  9. 7 5 4
  10. 5 4 3
    到这里基本想法就结束了，剩下的就是怎么实现的问题了。对于不同的要求，有不同的实现。

第一种：最简单的模拟，用一个单链表表示 LRU 的大小，表头存最旧的页面，表尾存最新的页面，然后每次 get 和 put 的时候，都遍历一次单链表进行相应操作。由于每次都要遍历单链表，所以每次操作都是 O（L）的复杂度，其中 L 表示 LRU 的大小。代码如下

typedef struct {
    int key;
    int val;
} elem;
class LRUCache{
public:
    elem *arr;  // lru cache
    int sz; // total number of elements in the list currently.
    int cap; //capacity
    LRUCache(int capacity) {  //init LRUCache
        arr = new elem[capacity];  //
        sz = 0;
        cap = capacity;
 }
 /* move the used element to the end of list */
 void adjust(int a) {
     if (a == sz - 1) {//the last one
        return ;
     }
     elem cur = arr[a];
     for (int i = a; i lt; sz - 1; i ++) {
        arr[i] = arr[i + 1]; // move all elements after position a 1 step left
     }
     arr[sz - 1] = cur; // move arr[a] to the end
 }
 //get the value of key, return -1 if it doesn't exit
 int get(int key) {
     //iterate the whole list to find if the key exits
     for (int i = 0; i lt; sz; i ++) {
         if (arr[i].key == key) {
            int a = arr[i].val;
            adjust(i);
            return a; // existent key
         }
    }
    return -1;
 }
 //update the key/value
 void set(int key, int value) {
     for (int i = 0; i lt; sz; i ++) {
         if (arr[i].key == key) { // existent
            arr[i].val = value; //update value ,and adjust the list
            adjust(i);
            return;
         }
     }
     if (sz == cap) { // check if reach the capacity
         for (int i = 0; i lt; sz - 1; i ++) {
             arr[i] = arr[i + 1]; // delete the least used element
         }
         arr[sz - 1].key = key;
         arr[sz - 1].val = value;
     } else {
         arr[sz].key = key;
         arr[sz].val = value;
         sz ++; // increase the size
     }
 }
};

第二种写法就是用双链表存 LRU 中保存的实际内容，然后用 HASH 表保存每一个 key 所对应的内容在双链表中的位置，其中双链表还是表头存最旧的，表尾存最新的，用 HASH 就可以加速查找，用双链表则是更新的时候可以达到 O(1)[单链表不能获得前驱节点的信息]，如果这里用 map 实现，而不是 hash_map 的话，那么复杂度是 log(L)，这个是由 map 的复杂度决定的。代码如下：

#include 
#include 
#include 

using namespace std;
using namespace stdext;

template
struct LRUCacheEntry
{
    K key;
    T data;
    LRUCacheEntry* prev;
    LRUCacheEntry* next;
};

template
class LRUCache
{
private:
    hash_map< K, LRUCacheEntry<K,T>* > _mapping;
    vector< LRUCacheEntry<K,T>* > _freeEntries;
    LRUCacheEntry * head;
    LRUCacheEntry * tail;
    LRUCacheEntry * entries;
public:
    LRUCache(size_t size){
    entries = new LRUCacheEntry[size];
    for (int i=0; i;
    tail = new LRUCacheEntry;
    head->prev = NULL;
    head->next = tail;
    tail->next = NULL;
    tail->prev = head;
 }
 ~LRUCache()
 {
    delete head;
    delete tail;
    delete [] entries;
 }
 void put(K key, T data)
 {
    LRUCacheEntry* node = _mapping[key];
    if(node)
      {
        // refresh the link list
        detach(node);
        node->data = data;
        attach(node);
      }
    else{
       if ( _freeEntries.empty() )
         {// lru cache is full
             node = tail->prev;
             detach(node);//delete a node
             _mapping.erase(node->key);
             node->data = data;
             node->key = key;
             _mapping[key] = node;
             attach(node);//add the new node
         }
       else{
             node = _freeEntries.back();
             _freeEntries.pop_back();
             node->key = key;
             node->data = data;
             _mapping[key] = node;
             attach(node);
           }
       }
 }

 T get(K key)
 {
      LRUCacheEntry* node = _mapping[key];
      if(node)
        {//if node is already in, refresh the double-link-list
           detach(node);
           attach(node);
           return node->data;
        }
       else return NULL;
 }

private:
    void detach(LRUCacheEntry* node)
    {// delete the node from the double-link-list
         node->prev->next = node->next;
         node->next->prev = node->prev;
    }
    void attach(LRUCacheEntry* node)
    {//add node to the head of double-link-list
         node->next = head->next;
         node->prev = head;
         head->next = node;
         node->next->prev = node;
    }
};

第二种方法利用双链表保存实际的 cache 内容，然后用 hash 来加速查找，hash 存的是每一个 key/value 的地址，这样就可以直接找到相应的 key/value 元素了。这种方法中，查找的复杂度是 O(1)，更新的复杂度，只需要进行一次查找，一次 detach，一次 attach，所以也是 O(1)的，较之第一种方法的优势就体现出来了。

最后，如果你想看下自己写的 LRU 是否正确，速度如何，可以在 Leetcode 上进行提交，地址：https://oj.leetcode.com/problems/lru-cache/，提交之后可以查看是否正确，正确的话，查看用时多少（第一种方法，可能可以在 Leetcode 上通过，也可能会得到一个 Time Limit Exceeded 的结果，这个就看你人品了）

Reference

Implement a LRU Cache in C++

Comments

▲