实现LRU缓存算法

2018-09-04 0 条评论 346 次阅读 0 人点赞

不积跬步无以至千里

1. 需求说明

LRU,全称Least Recently Used 近期最少使用,是开源世界里最常用的缓存算法,应用范围非常广泛,例如:HTTP缓存服务器工具 -- Squid、LVS、Redis淘汰键的规则、Memcached等。它的处理逻辑:删除那些最少被使用的条目。

当我们在不能使用第三方缓存工具的前提下,我们可以编写自己的LRU,让它服务于你的应用,提升应用的性能。

2. 实现落地

本次方案采用Python语言来实现:

# Author: Vincent.chan
# Blog: http://blog.alys114.com

from collections import OrderedDict

class LRU(OrderedDict):
 '''
 LRU Least Recently Used 近期最少使用
 处理逻辑:
 1. 每次添加都删除后追加,这样的话,使用少的key就会被推到最左边;
 2. 当元素个数超过容量时,就会删除最左边的元素;
 '''
 def __init__(self,size=10):
  self.size = size


 def set(self,key):
  if key in self:
   del self[key]

  self[key] = 1
  if len(self) > self.size:
   self.popitem(last=False)

d = LRU(3)
d.set('Python')
d.set('Go')
d.set('Shell')
print(d)
d.set('Go') # 内部顺序:Go|Python|Shell
d.set('Python') # 内部顺序:Python|Go|Shell
d.set('Groovy') # 内部顺序:Groovy|Go|Python (Shell)被踢掉
print(d)

''' 运行结果
LRU([('Python', 1), ('Go', 1), ('Shell', 1)])
LRU([('Go', 1), ('Python', 1), ('Groovy', 1)])
'''

补充说明:OrderedDict 是Python的高性能容器之一,是dict的子类,它记录了关键字插入的顺序。

掌柜

让未来超越过去!

文章评论(0)