欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

python实现LRU热点缓存

程序员文章站 2022-04-21 17:27:39
基于列表+Hash的LRU算法实现。 访问某个热点时,先将其从原来的位置删除,再将其插入列表的表头 为使读取及删除操作的时间复杂度为O(1),使用hash存储热点的信息的键值 访问某个热点时,先将其从原来的位置删除,再将其插入列表的表头 为使读取及删除操作的时间复杂度为O(1),使用hash存储热点 ......

基于列表+hash的lru算法实现。

  • 访问某个热点时,先将其从原来的位置删除,再将其插入列表的表头

  • 为使读取及删除操作的时间复杂度为o(1),使用hash存储热点的信息的键值

 

 class lrucaceh():
     def __init__(self, size=5):
         '''
         默认队列的长度为5
         使用列表来维护,使用字典来查询
         '''
         self.size = size
         self.cache = dict()
         self.key = []
 ​
     def get(self, key):
         '''
         获取缓存中的key的值
         '''
         if self.cache.get(key):
             self.key.remove(key)
             self.key.insert(0, key)
             return self.cache[key]
         return none
 ​
     def set(self, key, value):
         '''
         设置缓存,实现缓存淘汰
         '''
         if self.cache.get(key):
             self.cache.pop(key)
             self.cache[key] = value
             self.key.remove(key)
             self.key.insert(0, key)
         elif len(self.key) == self.size:
             old_key = self.key.pop()
             self.key.insert(0, key)
             self.cache.pop(old_key)
             self.cache[key] = value
         else:
             self.key.insert(0, key)
             self.cache[key] = value