提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

Python实现的一个简单LRUcache

Python 实现 简单 一个 LruCache
2023-06-13 09:15:46 时间

起因：我的同事需要一个固定大小的cache，如果记录在cache中，直接从cache中读取，否则从数据库中读取。python的dict是一个非常简单的cache,但是由于数据量很大，内存很可能增长的过大，因此需要限定记录数，并用LRU算法丢弃旧记录。key是整型，value是10KB左右的python对象

分析：

1）可以想到，在对于cache，我们需要维护key->value的关系

2）而为了实现LRU，我们又需要一个基于时间的优先级队列，来维护  timestamp ->(key,value)的关系

3）当cache中的记录数达到一个上界maxsize时，需要将timestamp最小的(key,value)出队列

4)当一个（key,value)被命中时，实际上我们需要将它从队列中，移除并插入到队列的尾部。

从分析可以看出我们的cache要达到性能最优需要满足上面的四项功能，对于队表的快速移除和插入，链表显然是最优的选择，为了快速移除，最好使用双向链表，为了插入尾部，需要有指向尾部的指针。

下面用python来实现：

复制代码代码如下:


#encoding=utf-8

classLRUCache(object):
   def__init__(self,maxsize):
       #cache的最大记录数
       self.maxsize=maxsize
       #用于真实的存储数据
       self.inner_dd={}
       #链表-头指针
       self.head=None
       #链表-尾指针
       self.tail=None

   defset(self,key,value):
       #达到指定大小     
       iflen(self.inner_dd)>=self.maxsize:
           self.remove_head_node()

       node=Node()
       node.data=(key,value)
       self.insert_to_tail(node)
       self.inner_dd[key]=node

   definsert_to_tail(self,node):
       ifself.tailisNone:
           self.tail=node
           self.head=node
       else:
           self.tail.next=node
           node.pre=self.tail
           self.tail=node

   defremove_head_node(self):
       node=self.head
       delself.inner_dd[node.data[0]]
       node=None
       self.head=self.head.next
       self.head.pre=None
   defget(self,key):
       ifkeyinself.inner_dd:
           #如果命中,需要将对应的节点移动到队列的尾部
           node=self.inner_dd.get(key)
           self.move_to_tail(node)
           returnnode.data[1]
       returnNone

   defmove_to_tail(self,node):
       #只需处理在队列头部和中间的情况
       ifnot(node==self.tail):
           ifnode==self.head:
               self.head=node.next
               self.head.pre=None
               self.tail.next=node
               node.pre=self.tail
               node.next=None
               self.tail=node
           else:
               pre_node=node.pre
               next_node=node.next
               pre_node.next=next_node
               next_node.pre=pre_node

               self.tail.next=node
               node.pre=self.tail
               node.next=None
               self.tail=node

classNode(object):
   def__init__(self):
       self.pre=None
       self.next=None
       #(key,value)
       self.data=None

   def__eq__(self,other):
       ifself.data[0]==other.data[0]:
           returnTrue
       returnFalse
   def__str__(self):
      returnstr(self.data)

if__name__=="__main__":
   cache=LRUCache(10)
   foriinxrange(1000):
       cache.set(i,i+1)
       cache.get(2)
   forkeyincache.inner_dd:
       printkey,cache.inner_dd[key]

相关文章