Python实现LRU算法的2种方法
作者:junjie 发布时间:2021-10-19 11:30:32
LRU:least recently used,最近最少使用算法。它的使用场景是:在有限的空间中存储对象时,当空间满时,会按一定的原则删除原有的对象,常用的原则(算法)有LRU,FIFO,LFU等。在计算机的Cache硬件,以及主存到虚拟内存的页面置换,还有Redis缓存系统中都用到了该算法。我在一次面试和一个笔试时,也遇到过这个问题。
LRU的算法是比较简单的,当对key进行访问时(一般有查询,更新,增加,在get()和set()两个方法中实现即可)时,将该key放到队列的最前端(或最后端)就行了,这样就实现了对key按其最后一次访问的时间降序(或升序)排列,当向空间中增加新对象时,如果空间满了,删除队尾(或队首)的对象。
在Python中,可以使用collections.OrderedDict很方便的实现LRU算法,当然,如果你想不到用OrderedDict,那可以用dict+list来实现。本文主要参考了LRU CACHE IN PYTHON,写的非常好,既实现了功能,又简洁易读。方法一的代码与参考文章基本相同,方法二是我自己想出来的,比较繁琐一些,其实OrderedDict本身也是类似的这种机制来实现的有序。
不过,下面的实现是有问题的,这个cache的key:value键值对中,value只能是不可变类型。因为,如果value是可变类型,那对于同一个key,所有调用get(key)方法返回的value都是指向同一个可变对象的,当修改其中一个value时,那所有的value都会被修改了,即使你没有调用set()方法也会这样。这是我们不希望看到的。解决方法我想到了两种,一是可变对象序列化后再存储,即将可变对象转为不可变对象;二是仍存储可变对象,但get()时,返回一个深拷贝,这样每个get()调用返回的对象就不会相互影响了。推荐第一种方法。另外,对于key,推荐使用str/unicode类型。
当并发时,还会存在一个问题,因为这涉及到对公共资源的写操作,所以必须要对set()加锁。其实,在并 * 况下,所有对公共资源的写操作都要加锁。如果不存在并发的情况,只有单线程,那可以不加锁。
方法一:用OrderedDict实现(推荐)
from collections import OrderedDict
class LRUCache(OrderedDict):
'''不能存储可变类型对象,不能并发访问set()'''
def __init__(self,capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self,key):
if self.cache.has_key(key):
value = self.cache.pop(key)
self.cache[key] = value
else:
value = None
return value
def set(self,key,value):
if self.cache.has_key(key):
value = self.cache.pop(key)
self.cache[key] = value
else:
if len(self.cache) == self.capacity:
self.cache.popitem(last = False) #pop出第一个item
self.cache[key] = value
else:
self.cache[key] = value
测试代码如下
c = LRUCache(5)
for i in range(5,10):
c.set(i,10*i)
print c.cache, c.cache.keys()
c.get(5)
c.get(7)
print c.cache, c.cache.keys()
c.set(10,100)
print c.cache, c.cache.keys()
c.set(9,44)
print c.cache, c.cache.keys()
输出如下
OrderedDict([(5, 50), (6, 60), (7, 70), (8, 80), (9, 90)]) [5, 6, 7, 8, 9]
OrderedDict([(6, 60), (8, 80), (9, 90), (5, 50), (7, 70)]) [6, 8, 9, 5, 7]
OrderedDict([(8, 80), (9, 90), (5, 50), (7, 70), (10, 100)]) [8, 9, 5, 7, 10]
OrderedDict([(8, 80), (5, 50), (7, 70), (10, 100), (9, 90)]) [8, 5, 7, 10, 9]
方法二:用dict+list实现(不推荐)
class LRUCache(object):
'''不能存储可变类型对象,不能并发访问set()'''
def __init__(self,capacity):
self.l = []
self.d = {}
self.capacity = capacity
def get(self,key):
if self.d.has_key(key):
value = self.d[key]
self.l.remove(key)
self.l.insert(0,key)
else:
value = None
return value
def set(self,key,value):
if self.d.has_key(key):
self.l.remove(key)
elif len(self.d) == self.capacity:
oldest_key = self.l.pop()
self.d.pop(oldest_key)
self.d[key] = value
self.l.insert(0, key)
测试代码如下
c = LRUCache(5)
for i in range(5,10):
c.set(i,10*i)
print c.d,c.l
c.get(5)
c.get(7)
print c.d,c.l
c.set(10,100)
print c.d,c.l
c.set(9,44)
print c.d,c.l
输出为
{8: 80, 9: 90, 5: 50, 6: 60, 7: 70} [9, 8, 7, 6, 5]
{8: 80, 9: 90, 5: 50, 6: 60, 7: 70} [7, 5, 9, 8, 6]
{5: 50, 7: 70, 8: 80, 9: 90, 10: 100} [10, 7, 5, 9, 8]
{5: 50, 7: 70, 8: 80, 9: 44, 10: 100} [9, 10, 7, 5, 8]
猜你喜欢
- plt.imshow(image)无法显示图片的解决使用plt.imshow()发现不能显示图片,加了plt.show()也还是不能显示先引
- 本文实例讲述了Python Datetime模块和Calendar模块用法。分享给大家供大家参考,具体如下:datetime模块1.1 概述
- 1、终极方法:条件注释<!--[if lte IE 6]> 这段文字仅显示在 IE6及IE6以下版本。 <![endif]
- 最近开始学习Python,但只限于看理论,编几行代码,觉得没有意思,就想能不能用Python编写可视化的界面。遂查找了相关资料,发现了PyQ
- 语言的内存管理是语言设计的一个重要方面。它是决定语言性能的重要因素。无论是C语言的手工管理,还是Java的垃圾回收,都成为语言最重要的特征。
- 介绍分面是指事物的多维度属性。例如一本书包含主题、作者、年代等分面。而分面搜索是指通过事物的这些属性不断筛选、过滤搜索结果的方法。可以将分面
- 为cd2sc.com网站功能而开发,代码为本人原创,生成速度一般。 (出于众所周知的原因,涉及到数据库的数据字段名称做了改动,并且为了代码明
- 不通过数据源名DSN也能访问Access数据库吗?代码如下:<% dim conn &nbs
- 代码如下:---ntext数据类型字符替换 create table tt ( sid INT IDENTITY(1,1), c
- 表单的验证一直是网页设计者头痛的问题,表单验证类 Validator就是为解决这个问题而写的,旨在使设计者从纷繁复杂的表单验证中解放出来,把
- 英文文档:staticmethod(function)Return a static method for function.A stati
- Symfony2是一个基于PHP语言的Web开发框架,有着开发速度快、性能高等特点。本文以一个程序示例的实现过程详细叙述了Symfony2框
- 一、前言上次写了一个俄罗斯方块,感觉好像大家都看懂了,这次就更新一个植物大战僵尸吧二、引入模块import pygameimport ran
- 没人愿意等待。所以,没有访问者真的能够忍受一个打开速度极慢的网站。但是,网页打开速度到底对用户行为有什么影响,恐怕没几个人能够说清楚吧。前几
- 爬虫数据保存到mongoDB的方法:import pymongo# 首先需要注意,mongodb数据库存储的类型是以键值
- 异步编程带来的问题在客户端Javascript中并不明显,但随着服务器端Javascript越来越广的被使用,大量的异步IO操作使得该问题变
- #-*- coding: utf-8 -*-import win32api,win32gui, win32conimport osimpor
- Data Points Archive 有时, 为了让应用程序运行得更快,所做的全部工作就是在这里或那里做一些很小调整。啊,但关键在于确定如
- 通过第三方BeautifulSoup库来爬取op.gg网页静态数据主要思路op.gg网站网站以出场率高低排名,并且列出对位胜率,在高出场率的
- 1.首先主题选择不要落俗!现在许多的个人主页就象“大锅饭”。题材包罗万象,内容雷同无味。人人都是“软件速递”“音乐宝库”“主页教程”等等。让