LRU Cache

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.

tag: data structure

10/8/2015 update

Use a hash map and linked list to implement an algorithm with O(1) time complexity in both set() and get().

With a hash map, get is o(1) and set is o(1) is capacity is infinite.

With a linked list, set is o(1)(no duplicates) and get is o(n).

So we need to combine these two data structures.

hash map stores key-TreeNode pair

class Node{
public:
  int key;
  int val;
  Node * next, * prev;
  Node(int k, int v):key(k), val(v), next(nullptr), prev(nullptr){}
};
class LRUCache{
public:
    Node * head, * tail;//head is the most recently used node. Tail is the least recently used.
    int size;
    int capacity;
    unordered_map<int, Node *> map;
    LRUCache(int capacity) {
        this->size = 0;
        this->capacity = capacity;
        this->head = this->tail = nullptr;
        map.clear();
    }
    
    int get(int key) {
        Node * node;
        if(map.find(key) == map.end()){
            return -1;
        }
        else{
            //find in cache
            node = map[key];
            if(size == 1 || node == head){
                return node->val;
            }
            //size is more than 1, and node is not head
            
            node->prev->next = node->next;
            if(node == tail){
                //move tail
                tail = tail->prev;
                tail->next = nullptr;
            }
            else{
                node->next->prev = node->prev;
            }
            //move node to head
            node->next = head;
            head->prev = node;
            node->prev = nullptr;
            head = node;
            return head->val;
        }
    }
    
    void set(int key, int value) {
        if(capacity == 0) return ;
        if(map.find(key) != map.end()){
            //found in list
            map[key]->val = value;
            get(key);
        }
        else{
            //not found in key
            //connect it to head
            Node * node = new Node(key, value);
            map[key] = node;
            if(size == 0){
                head = tail = node;
            }
            else{
                node->next = head;
                head->prev = node;
                head = node;
            }
            if(size == capacity){
                //delete tail
                map.erase(tail->key);
                tail = tail->prev;
                delete tail->next;
                tail->next = nullptr;
            }
            else{
                size++;
            }
        }
    }
};

看到这题，想起计算机体系结构课上，老师讲过的全相连(full-associate)，组相连(set-associate)，直接映射(direct map)。此题涉及了LRU，肯定不是直接映射或组相连。只能是全相连。

先暴力尝试，get和set都是O(n)。时间超界。

版本一

class node{
public:
    int key;
    int val;
    int n;
    node(int k, int v, int n): key(k), val(v), n(n) {}
};
class LRUCache{
public:
    unsigned int count;//overflow bug
    int size;
    int capacity;
    vector<node *> cache;
    LRUCache(int capacity) {
        this->capacity = capacity;
        this->size = 0;
        this->count = 0;
    }
    
    int get(int key) {//O(n)
        vector<node*>::iterator it;
        for(it = cache.begin(); it != cache.end(); it++){
            if ((*it)->key == key){
                (*it)->n = count++;
                return (*it)->val;
            }
        }
        return -1;
    }
    
    void set(int key, int value) {//O(n)
        vector<node*>::iterator it;
        vector<node*>::iterator minIt = cache.begin();
        for(it = cache.begin(); it != cache.end(); it++){
            if((*it)->key == key){
                (*it)->val = value;
                (*it)->n = count++;
                return;
            }
            else{
                if((*minIt)->n > (*it)->n){
                    minIt = it;
                }
            }
        }
        if(size < capacity){
            node * p = new node(key, value, count++);
            size++;
            cache.push_back(p);
        }
        else{//full
            (*minIt)->val = value;
            (*minIt)->key = key;
            (*minIt)->n = count++;
        }
    }
};

尝试优化中。

版本二，参照了这个博客：http://www.cnblogs.com/dolphin0520/p/3741519.html

用一个链表和哈希表，实现了get和set的o(1)复杂度。

链表内的元素按照访问时间由新到旧排列。

新的在表头，最旧的在末尾。当链表满了时，删掉末尾节点，插入新数据。

当其中的某个节点被访问时，取出该节点，放到链表头。

哈希表里存着key-node指针对，方便在o(1)时间内找到节点。

我的方案里重写了底层的链表接口。也可以直接用STL里的list，和unordered_map<int, lsit<node*>::iterator>。

善用iterator，它是个好东西。

class node{
public:
  int key;
  int val;
  node * next;
  node * prev;
  node(int k, int v): key(k), val(v), next(NULL), prev(NULL){}
};
class myList{
public:
  int size;
  node * head;
  node * tail;
  myList():size(0), head(NULL), tail(NULL){}
  void remove_tail(){
      node * p = tail;
      remove(p);
      delete p;
  }
  node * get_tail(){
      return tail;
  }
  void remove(node * p){
      if(p != head){
          p->prev->next = p->next;
      }
      if(p != tail){
          p->next->prev = p->prev;
      }
      if(p == head){
          head = p->next;
          if(head != NULL){
              head->prev = NULL;
          }
      }
      if(p == tail){
          tail = p->prev;
          if(tail != NULL){
              tail->next = NULL;
          }
      }
      size--;
  }
  void push_front(node * p){
      if(size == 0){
          head = tail = p;
          p->next = p->prev = NULL;
          size++;
      }
      else{
          p->next = head;
          head->prev = p;
          p->prev = NULL;
          head = p;
          size++;
      }
  }
};
class LRUCache{
public:
    unordered_map <int, node *> hashMap;
    myList* l = new myList();
    int capacity;
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    int get(int key) {
        if(hashMap.find(key) != hashMap.end()){//found
            node * p = hashMap[key];
            l->remove(p);
            l->push_front(p);
            return p->val;
        }
        else{//not found
            return-1;
        }
    }
    
    void set(int key, int value) {
        if(get(key) != -1){//exist
            hashMap[key]->val = value;
        }
        else{//not exist
            node * p = new node(key, value);
            if(l->size < capacity){//not full
                l->push_front(p);
            }
            else{//full
                int tailKey = l->get_tail()->key;
                l->remove_tail();
                hashMap.erase(tailKey);
                l->push_front(p);       
            }
            hashMap[key] = p;
        }
    }
};