LRU Cache

[复制链接]
292|10
 楼主 | 2019-9-15 20:03 | 显示全部楼层 |阅读模式
  • 题目链接:https://oj.leetcode.com/problems/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.
  • 题目大意:为LRU Cache设计一个数据结构,它支持两个操作:
   1)get(key):如果key在cache中,则返回对应的value值,否则返回-1
   2)set(key,value):如果key不在cache中,则将该(key,value)插入cache中(注意,如果cache已满,则必须把最近最久未使用的元素从cache中删除);如果key在cache中,则重置value的值。

使用特权

评论回复
 楼主 | 2019-9-15 20:03 | 显示全部楼层
解题思路:题目让设计一个LRU Cache,即根据LRU算法设计一个缓存。在这之前需要弄清楚LRU算法的核心思想,LRU全称是Least
Recently Used,即最近最久未使用的意思。在操作系统的内存管理中,有一类很重要的算法就是内存页面置换算法(包括FIFO,LRU,LFU等几种常见页面置换算法)。事实上,Cache算法和内存页面置换算法的核心思想是一样的:都是在给定一个限定大小的空间的前提下,设计一个原则如何来更新和访问其中的元素。下面说一下LRU算法的核心思想,LRU算法的设计原则是:如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小。也就是说,当限定的空间已存满数据时,应当把最久没有被访问到的数据淘汰。

  而用什么数据结构来实现LRU算法呢?可能大多数人都会想到:用一个数组来存储数据,给每一个数据项标记一个访问时间戳,每次插入新数据项的时候,先把数组中存在的数据项的时间戳自增,并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候,将被访问的数据项的时间戳置为0。当数组空间已满时,将时间戳最大的数据项淘汰。

  这种实现思路很简单,但是有什么缺陷呢?需要不停地维护数据项的访问时间戳,另外,在插入数据、删除数据以及访问数据时,时间复杂度都是O(n)。

  那么有没有更好的实现办法呢?

  那就是利用链表和hashmap。当需要插入新的数据项的时候,如果新数据项在链表中存在(一般称为命中),则把该节点移到链表头部,如果不存在,则新建一个节点,放到链表头部,若缓存满了,则把链表最后一个节点删除即可。在访问数据的时候,如果数据项在链表中存在,则把该节点移到链表头部,否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。

使用特权

评论回复
 楼主 | 2019-9-15 20:04 | 显示全部楼层
  总结一下:根据题目的要求,LRU Cache具备的操作:

  1)set(key,value):如果key在hashmap中存在,则先重置对应的value值,然后获取对应的节点cur,将cur节点从链表删除,并移动到链表的头部;若果key在hashmap不存在,则新建一个节点,并将节点放到链表的头部。当Cache存满的时候,将链表最后一个节点删除即可。

  2)get(key):如果key在hashmap中存在,则把对应的节点放到链表头部,并返回对应的value值;如果不存在,则返回-1。

  仔细分析一下,如果在这地方利用单链表和hashmap,在set和get中,都有一个相同的操作就是将在命中的节点移到链表头部,如果按照传统的遍历办法来删除节点可以达到题目的要求么?第二,在删除链表末尾节点的时候,必须遍历链表,然后将末尾节点删除,这个能达到题目的时间要求么?

使用特权

评论回复
 楼主 | 2019-9-15 20:04 | 显示全部楼层
 试一下便知结果:

  第一个版本实现:

  1. #include <iostream>
  2. #include <map>
  3. #include <algorithm>
  4. using namespace std;

  5. struct Node
  6. {
  7.     int key;
  8.     int value;
  9.     Node *next;
  10. };


  11. class LRUCache{
  12. private:
  13.     int count;
  14.     int size ;
  15.     map<int,Node *> mp;
  16.     Node *cacheList;
  17. public:
  18.     LRUCache(int capacity) {
  19.       size = capacity;
  20.       cacheList = NULL;
  21.       count = 0;
  22.     }
  23.      
  24.     int get(int key) {
  25.         if(cacheList==NULL)
  26.             return -1;
  27.         map<int,Node *>::iterator it=mp.find(key);
  28.         if(it==mp.end())  //如果在Cache中不存在该key, 则返回-1
  29.         {
  30.             return -1;
  31.         }
  32.         else
  33.         {
  34.             Node *p = it->second;   
  35.             pushFront(p);    //将节点p置于链表头部
  36.         }
  37.         return cacheList->value;  
  38.     }
  39.      
  40.     void set(int key, int value) {
  41.         if(cacheList==NULL)   //如果链表为空,直接放在链表头部
  42.         {
  43.             cacheList = (Node *)malloc(sizeof(Node));
  44.             cacheList->key = key;
  45.             cacheList->value = value;
  46.             cacheList->next = NULL;
  47.             mp[key] = cacheList;
  48.             count++;
  49.         }
  50.         else   //否则,在map中查找
  51.         {
  52.             map<int,Node *>::iterator it=mp.find(key);
  53.             if(it==mp.end())   //没有命中
  54.             {
  55.                 if(count == size)  //cache满了
  56.                 {
  57.                     Node * p = cacheList;
  58.                     Node *pre = p;
  59.                     while(p->next!=NULL)
  60.                     {
  61.                         pre = p;
  62.                         p= p->next;
  63.                     }
  64.                     mp.erase(p->key);
  65.                     count--;
  66.                     if(pre==p)         //说明只有一个节点
  67.                         p=NULL;
  68.                     else
  69.                         pre->next = NULL;
  70.                     free(p);
  71.                 }
  72.                 Node * newNode = (Node *)malloc(sizeof(Node));
  73.                 newNode->key = key;
  74.                 newNode->value = value;
  75.                  
  76.                 newNode->next = cacheList;
  77.                 cacheList = newNode;
  78.                  
  79.                 mp[key] = cacheList;
  80.                 count++;   
  81.             }
  82.             else
  83.             {
  84.                 Node *p = it->second;   
  85.                 p->value = value;
  86.                 pushFront(p);
  87.             }
  88.         }
  89.          
  90.     }
  91.      
  92.     void pushFront(Node *cur)   //单链表删除节点,并将节点移动链表头部,O(n)
  93.     {
  94.         if(count==1)
  95.             return;
  96.         if(cur==cacheList)
  97.             return;
  98.         Node *p = cacheList;
  99.         while(p->next!=cur)
  100.         {
  101.             p=p->next;      
  102.         }
  103.         p->next = cur->next;   //删除cur节点
  104.             
  105.         cur->next = cacheList;
  106.         cacheList = cur;
  107.     }
  108.      
  109.     void printCache(){
  110.          
  111.         Node *p = cacheList;
  112.         while(p!=NULL)
  113.         {
  114.             cout<<p->key<<" ";
  115.             p=p->next;
  116.         }
  117.         cout<<endl;
  118.     }
  119. };


  120. int main(void)
  121. {
  122.     /*LRUCache cache(3);
  123.     cache.set(2,10);
  124.     cache.printCache();
  125.     cache.set(1,11);
  126.     cache.printCache();
  127.     cache.set(2,12);
  128.     cache.printCache();
  129.     cache.set(1,13);
  130.     cache.printCache();
  131.     cache.set(2,14);
  132.     cache.printCache();
  133.     cache.set(3,15);
  134.     cache.printCache();
  135.     cache.set(4,100);
  136.     cache.printCache();
  137.     cout<<cache.get(2)<<endl;
  138.     cache.printCache();*/
  139.      
  140.     LRUCache cache(2);
  141.     cout<<cache.get(2)<<endl;
  142.     cache.set(2,6);
  143.     cache.printCache();
  144.     cout<<cache.get(1)<<endl;
  145.     cache.set(1,5);
  146.     cache.printCache();
  147.     cache.set(1,2);
  148.     cache.printCache();
  149.     cout<<cache.get(1)<<endl;
  150.     cout<<cache.get(2)<<endl;
  151.     return 0;
  152. }
复制代码

使用特权

评论回复
 楼主 | 2019-9-15 20:04 | 显示全部楼层
提交之后,提示超时:

442825d7e28e84fbff.png

  因此要对算法进行改进,如果把pushFront时间复杂度改进为O(1)的话是不是就能达到要求呢?

  但是  在已知要删除的节点的情况下,如何在O(1)时间复杂度内删除节点?

  如果知道当前节点的前驱节点的话,则在O(1)时间复杂度内删除节点是很容易的。而在无法获取当前节点的前驱节点的情况下,能够实现么?对,可以实现的。

使用特权

评论回复
 楼主 | 2019-9-15 20:05 | 显示全部楼层
  具体的可以参照这几篇博文:

  http://www.cnblogs.com/xwdreamer/archive/2012/04/26/2472102.html

  http://www.nowamagic.net/librarys/veda/detail/261

  原理:假如要删除的节点是cur,通过cur可以知道cur节点的后继节点curNext,如果交换cur节点和curNext节点的数据域,然后删除curNext节点(curNext节点是很好删除地),此时便在O(1)时间复杂度内完成了cur节点的删除。

  改进版本1:

  1. void pushFront(Node *cur)  //单链表删除节点,并将节点移动链表头部,O(1)
  2.     {
  3.         if(count==1)
  4.             return;
  5.         //先删除cur节点 ,再将cur节点移到链表头部
  6.         Node *curNext = cur->next;
  7.         if(curNext==NULL)  //如果是最后一个节点
  8.         {
  9.             Node * p = cacheList;
  10.             while(p->next!=cur)
  11.             {
  12.                 p=p->next;
  13.             }
  14.             p->next = NULL;
  15.             
  16.             cur->next = cacheList;
  17.             cacheList = cur;
  18.         }
  19.         else    //如果不是最后一个节点
  20.         {
  21.             cur->next = curNext->next;   
  22.             int tempKey = cur->key;
  23.             int tempValue = cur->value;
  24.             
  25.             cur->key = curNext->key;
  26.             cur->value = curNext->value;
  27.             
  28.             curNext->key = tempKey;
  29.             curNext->value = tempValue;
  30.             
  31.             curNext->next = cacheList;
  32.             cacheList  = curNext;
  33.             
  34.             mp[curNext->key] = curNext;
  35.             mp[cur->key] = cur;
  36.         }
  37.     }
复制代码

使用特权

评论回复
 楼主 | 2019-9-15 20:05 | 显示全部楼层
 提交之后,提示Accepted,耗时492ms,达到要求。

481215d7e2913dc03e.png

使用特权

评论回复
 楼主 | 2019-9-15 20:06 | 显示全部楼层
  有没有更好的实现办法,使得删除末尾节点的复杂度也在O(1)?那就是利用双向链表,并提供head指针和tail指针,这样一来,所有的操作都是O(1)时间复杂度。

  改进版本2:

  1. #include <iostream>
  2. #include <map>
  3. #include <algorithm>
  4. using namespace std;

  5. struct Node
  6. {
  7.     int key;
  8.     int value;
  9.     Node *pre;
  10.     Node *next;
  11. };


  12. class LRUCache{
  13. private:
  14.     int count;
  15.     int size ;
  16.     map<int,Node *> mp;
  17.     Node *cacheHead;
  18.     Node *cacheTail;
  19. public:
  20.     LRUCache(int capacity) {
  21.       size = capacity;
  22.       cacheHead = NULL;
  23.       cacheTail = NULL;
  24.       count = 0;
  25.     }
  26.      
  27.     int get(int key) {
  28.         if(cacheHead==NULL)
  29.             return -1;
  30.         map<int,Node *>::iterator it=mp.find(key);
  31.         if(it==mp.end())  //如果在Cache中不存在该key, 则返回-1
  32.         {
  33.             return -1;
  34.         }
  35.         else
  36.         {
  37.             Node *p = it->second;   
  38.             pushFront(p);    //将节点p置于链表头部
  39.         }
  40.         return cacheHead->value;  
  41.     }
  42.      
  43.     void set(int key, int value) {
  44.         if(cacheHead==NULL)   //如果链表为空,直接放在链表头部
  45.         {
  46.             cacheHead = (Node *)malloc(sizeof(Node));
  47.             cacheHead->key = key;
  48.             cacheHead->value = value;
  49.             cacheHead->pre = NULL;
  50.             cacheHead->next = NULL;
  51.             mp[key] = cacheHead;
  52.             cacheTail = cacheHead;
  53.             count++;
  54.         }
  55.         else   //否则,在map中查找
  56.         {
  57.             map<int,Node *>::iterator it=mp.find(key);
  58.             if(it==mp.end())   //没有命中
  59.             {
  60.                 if(count == size)  //cache满了
  61.                 {
  62.                     if(cacheHead==cacheTail&&cacheHead!=NULL)  //只有一个节点
  63.                     {
  64.                         mp.erase(cacheHead->key);
  65.                         cacheHead->key = key;
  66.                         cacheHead->value = value;
  67.                         mp[key] = cacheHead;
  68.                     }
  69.                     else
  70.                     {
  71.                         Node * p =cacheTail;
  72.                         cacheTail->pre->next = cacheTail->next;  
  73.                         cacheTail = cacheTail->pre;

  74.                         mp.erase(p->key);
  75.                      
  76.                         p->key= key;
  77.                         p->value = value;
  78.                      
  79.                         p->next = cacheHead;
  80.                         p->pre = cacheHead->pre;
  81.                         cacheHead->pre = p;
  82.                         cacheHead = p;
  83.                         mp[cacheHead->key] = cacheHead;
  84.                     }
  85.                 }
  86.                 else
  87.                 {
  88.                     Node * p = (Node *)malloc(sizeof(Node));
  89.                     p->key = key;
  90.                     p->value = value;
  91.                      
  92.                     p->next = cacheHead;
  93.                     p->pre = NULL;
  94.                     cacheHead->pre = p;
  95.                     cacheHead = p;
  96.                     mp[cacheHead->key] = cacheHead;
  97.                     count++;
  98.                 }
  99.             }
  100.             else
  101.             {
  102.                 Node *p = it->second;   
  103.                 p->value = value;
  104.                 pushFront(p);
  105.             }
  106.         }
  107.          
  108.     }

  109.      
  110.     void pushFront(Node *cur)   //双向链表删除节点,并将节点移动链表头部,O(1)
  111.     {
  112.         if(count==1)
  113.             return;
  114.         if(cur==cacheHead)
  115.             return;
  116.             
  117.         if(cur==cacheTail)
  118.         {
  119.             cacheTail = cur->pre;
  120.         }
  121.          
  122.         cur->pre->next = cur->next;   //删除节点
  123.         if(cur->next!=NULL)
  124.             cur->next->pre = cur->pre;
  125.          
  126.         cur->next = cacheHead;
  127.         cur->pre = NULL;
  128.         cacheHead->pre = cur;
  129.         cacheHead = cur;   
  130.     }
  131.      
  132.     void printCache(){
  133.          
  134.         Node *p = cacheHead;
  135.         while(p!=NULL)
  136.         {
  137.             cout<<p->key<<" ";
  138.             p=p->next;
  139.         }
  140.         cout<<endl;
  141.     }
  142. };


  143. int main(void)
  144. {
  145.     LRUCache cache(3);
  146.     cache.set(1,1);
  147.     //cache.printCache();
  148.      
  149.     cache.set(2,2);
  150.     //cache.printCache();
  151.      
  152.     cache.set(3,3);
  153.     cache.printCache();
  154.      
  155.     cache.set(4,4);
  156.     cache.printCache();
  157.      
  158.     cout<<cache.get(4)<<endl;
  159.     cache.printCache();
  160.      
  161.     cout<<cache.get(3)<<endl;
  162.     cache.printCache();
  163.     cout<<cache.get(2)<<endl;
  164.     cache.printCache();
  165.     cout<<cache.get(1)<<endl;
  166.     cache.printCache();
  167.      
  168.     cache.set(5,5);
  169.     cache.printCache();
  170.      
  171.     cout<<cache.get(1)<<endl;
  172.     cout<<cache.get(2)<<endl;
  173.     cout<<cache.get(3)<<endl;
  174.     cout<<cache.get(4)<<endl;
  175.     cout<<cache.get(5)<<endl;
  176.      
  177.     return 0;
  178. }
复制代码

使用特权

评论回复
 楼主 | 2019-9-15 20:06 | 显示全部楼层
提交测试结果:

719955d7e293bae7eb.png

  可以发现,效率有进一步的提升。

使用特权

评论回复
 楼主 | 2019-9-15 20:06 | 显示全部楼层
  其实在STL中的list就是一个双向链表,如果希望代码简短点,可以用list来实现:

  具体实现:

  1. #include <iostream>
  2. #include <map>
  3. #include <algorithm>
  4. #include <list>
  5. using namespace std;

  6. struct Node
  7. {
  8.     int key;
  9.     int value;
  10. };


  11. class LRUCache{
  12. private:
  13.     int maxSize ;
  14.     list<Node> cacheList;
  15.     map<int, list<Node>::iterator > mp;
  16. public:
  17.     LRUCache(int capacity) {
  18.       maxSize = capacity;
  19.     }
  20.      
  21.     int get(int key) {
  22.         map<int, list<Node>::iterator >::iterator it = mp.find(key);
  23.         if(it==mp.end())      //没有命中
  24.         {
  25.             return -1;
  26.         }
  27.         else  //在cache中命中了
  28.         {
  29.             list<Node>::iterator listIt = mp[key];
  30.             Node newNode;
  31.             newNode.key = key;
  32.             newNode.value = listIt->value;
  33.             cacheList.erase(listIt);               //先删除命中的节点      
  34.             cacheList.push_front(newNode);   //将命中的节点放到链表头部
  35.             mp[key] = cacheList.begin();
  36.         }
  37.         return cacheList.begin()->value;
  38.     }
  39.      
  40.     void set(int key, int value) {
  41.         map<int, list<Node>::iterator >::iterator it = mp.find(key);
  42.         if(it==mp.end())   //没有命中
  43.         {
  44.             if(cacheList.size()==maxSize)  //cache满了
  45.             {
  46.                 mp.erase(cacheList.back().key);   
  47.                 cacheList.pop_back();
  48.             }
  49.             Node newNode;
  50.             newNode.key = key;
  51.             newNode.value = value;
  52.             cacheList.push_front(newNode);
  53.             mp[key] = cacheList.begin();
  54.         }
  55.         else  //命中
  56.         {
  57.             list<Node>::iterator listIt = mp[key];
  58.             cacheList.erase(listIt);               //先删除命中的节点         
  59.             Node newNode;
  60.             newNode.key = key;
  61.             newNode.value = value;
  62.             cacheList.push_front(newNode);   //将命中的节点放到链表头部
  63.             mp[key] = cacheList.begin();
  64.         }
  65.     }
  66. };


  67. int main(void)
  68. {
  69.     LRUCache cache(3);
  70.     cache.set(1,1);
  71.      
  72.     cache.set(2,2);
  73.      
  74.     cache.set(3,3);
  75.      
  76.     cache.set(4,4);
  77.      
  78.     cout<<cache.get(4)<<endl;
  79.      
  80.     cout<<cache.get(3)<<endl;
  81.     cout<<cache.get(2)<<endl;
  82.     cout<<cache.get(1)<<endl;
  83.      
  84.     cache.set(5,5);
  85.      
  86.     cout<<cache.get(1)<<endl;
  87.     cout<<cache.get(2)<<endl;
  88.     cout<<cache.get(3)<<endl;
  89.     cout<<cache.get(4)<<endl;
  90.     cout<<cache.get(5)<<endl;
  91.      
  92.     return 0;
  93. }
复制代码

使用特权

评论回复
 楼主 | 2019-9-15 20:06 | 显示全部楼层
作者:Matrix海子
    
出处:http://www.cnblogs.com/dolphin0520/
    
本博客中未标明转载的文章归作者Matrix海子和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

使用特权

评论回复
扫描二维码,随时随地手机跟帖
您需要登录后才可以回帖 登录 | 注册

本版积分规则

我要发帖 投诉建议 创建版块 申请版主

快速回复

您需要登录后才可以回帖
登录 | 注册
高级模式

论坛热帖

关闭

热门推荐上一条 /3 下一条

在线客服 快速回复 返回顶部 返回列表