什么是LRU Cache

三个比方：

  1. 记忆，短时记忆，读取速度超快
  2. 钱包 - 储物柜
  3. 已经背下来的代码模块，读取速度就是O(1)

计算机三级缓存机制，位置在上面的读取速度更快

LRU的概念：

  1. Least Recently Used，“最远”使用页面置换算法
  2. Hash Table + Double LinkedList（哈希表+双向链表）
  3. O(1) get (Cache本身特性：一般只查最后一个元素，所以时间复杂度O(1))
  4. O(1) set (新增、更新)

LRU原理示意图

LRU淘汰示意图

如上图所示，LRU的结构类似于一个双端队列，元素从front进，rear出。最近新增或被访问的元素总是在队首，当缓存容量达到上限时，最久未被使用的元素就被去除掉了。

拓展——LFU

LFU全称是Least Frequently Used，即最不常用页面置换算法，其淘汰思想是在LRU的基础上为页面（队列元素）加上使用频次，依据最近一段时间内的使用频次来进行页面淘汰。

LFU淘汰示意图

如上图所示，LFU队列中的元素（页面），从front进，rear出。进入队列后，会根据最近使用频次（页面访问次数）进行排序，保证使用频次最高的元素（页面）总是在队首。当缓存容量达到上限时，队尾的元素，也就是最少读取到的页面，淘汰出局。

实战题目

  1. 设计和实现一个LRUCache

    • 无需真的构造一个双向链表，只要实现指定的方法即可

      class LRUCache(object):
def _init__( self, capacity ):
   self.dic = collections.OrderedDict()
   self.remain = capacity

def get(self, key):
   if key not in self.dic:
       return -1
   v = self.dic.pop( key)
   self.dic[key] = v#set key as the newest one
   return v

def put(self,key,value):
   if key in self.dic:
       self.dic.pop( key)
   else:
       if self.remain > 0:
           self.remain -= 1
       else:#self.dic is full
           self.dic.popitem(last=False)
   self.dic[key] = value

results matching ""

    No results matching ""