Python实现的最近最少使用算法
本文实例讲述了Python实现的最近最少使用算法。分享给大家供大家参考。具体如下：
#lrucache.py--asimpleLRU(Least-Recently-Used)cacheclass
#Copyright2004EvanProdromou<evan@bad.dynu.ca>
#LicensedundertheAcademicFreeLicense2.1
#LicensedforftputilundertherevisedBSDlicense
#withpermissionbytheauthor,EvanProdromou.Many
#thanks,Evan!:-)
#
#Theoriginalfileisavailableat
#http://pypi.python.org/pypi/lrucache/0.2.
#arch-tag:LRUcachemainmodule
"""asimpleLRU(Least-Recently-Used)cachemodule
ThismoduleprovidesverysimpleLRU(Least-Recently-Used)cache
functionality.
An*in-memorycache*isusefulforstoringtheresultsofan
'expe\nsive'process(onethattakesalotoftimeorresources)for
laterre-use.Typicalexamplesareaccessingdatafromthefilesystem,
adatabase,oranetworklocation.Ifyouknowyou'llneedtore-read
thedataagain,itcanhelptokeepitinacache.
You*can*useaPythondictionaryasacacheforsomepurposes.
However,iftheresultsyou'recachingarelarge,oryouhavealotof
possibleresults,thiscanbeimpracticalmemory-wise.
An*LRUcache*,ontheotherhand,onlykeeps_some_oftheresultsin
memory,whichkeepsyoufromoverusingresources.Thecacheisbounded
byamaximumsize;ifyoutrytoaddmorevaluestothecache,itwill
automaticallydiscardthevaluesthatyouhaven'treadorwrittento
inthelongesttime.Inotherwords,theleast-recently-useditemsare
discarded.[1]_
..[1]:'Discarded'heremeans'removedfromthecache'.
"""
from__future__importgenerators
importtime
fromheapqimportheappush,heappop,heapify
#thesuffixafterthehyphendenotesmodificationsbythe
#ftputilprojectwithrespecttotheoriginalversion
__version__="0.2-1"
__all__=['CacheKeyError','LRUCache','DEFAULT_SIZE']
__docformat__='reStructuredTexten'
DEFAULT_SIZE=16
"""DefaultsizeofanewLRUCacheobject,ifno'size'argumentisgiven."""
classCacheKeyError(KeyError):
"""Errorraisedwhencacherequestsfail
Whenacacherecordisaccessedwhichnolongerexists(orneverdid),
thiserrorisraised.Toavoidit,youmaywanttocheckfortheexistence
ofacacherecordbeforereadingordeletingit."""
pass
classLRUCache(object):
"""Least-Recently-Used(LRU)cache.
Instancesofthisclassprovidealeast-recently-used(LRU)cache.They
emulateaPythonmappingtype.YoucanuseanLRUcachemoreorlesslike
aPythondictionary,withtheexceptionthatobjectsyouputintothe
cachemaybediscardedbeforeyoutakethemout.
Someexampleusage::
cache=LRUCache(32)#newcache
cache['foo']=get_file_contents('foo')#orwhatever
if'foo'incache:#ifit'sstillincache...
#usecachedversion
contents=cache['foo']
else:
#recalculate
contents=get_file_contents('foo')
#storeincachefornexttime
cache['foo']=contents
printcache.size#Maximumsize
printlen(cache)#0<=len(cache)<=cache.size
cache.size=10#Auto-shrinkonsizeassignment
foriinrange(50):#note:largerthancachesize
cache[i]=i
if0notincache:print'Zerowasdiscarded.'
if42incache:
delcache[42]#Manualdeletion
forjincache:#iterate(inLRUorder)
printj,cache[j]#iteratorproduceskeys,notvalues
"""
class__Node(object):
"""Recordofacachedvalue.Notforpublicconsumption."""
def__init__(self,key,obj,timestamp,sort_key):
object.__init__(self)
self.key=key
self.obj=obj
self.atime=timestamp
self.mtime=self.atime
self._sort_key=sort_key
def__cmp__(self,other):
returncmp(self._sort_key,other._sort_key)
def__repr__(self):
return"<%s%s=>%s(%s)>"%\
(self.__class__,self.key,self.obj,\
time.asctime(time.localtime(self.atime)))
def__init__(self,size=DEFAULT_SIZE):
#Checkarguments
ifsize<=0:
raiseValueError,size
eliftype(size)isnottype(0):
raiseTypeError,size
object.__init__(self)
self.__heap=[]
self.__dict={}
"""Maximumsizeofthecache.
Ifmorethan'size'elementsareaddedtothecache,
theleast-recently-usedoneswillbediscarded."""
self.size=size
self.__counter=0
def_sort_key(self):
"""Returnanewintegervalueuponeverycall.
Cachenodesneedamonotonicallyincreasingtimeindicator.
time.time()andtime.clock()don'tguaranteethisina
platform-independentway.
"""
self.__counter+=1
returnself.__counter
def__len__(self):
returnlen(self.__heap)
def__contains__(self,key):
returnself.__dict.has_key(key)
def__setitem__(self,key,obj):
ifself.__dict.has_key(key):
node=self.__dict[key]
#updatenodeobjectin-place
node.obj=obj
node.atime=time.time()
node.mtime=node.atime
node._sort_key=self._sort_key()
heapify(self.__heap)
else:
#sizemayhavebeenreset,soweloop
whilelen(self.__heap)>=self.size:
lru=heappop(self.__heap)
delself.__dict[lru.key]
node=self.__Node(key,obj,time.time(),self._sort_key())
self.__dict[key]=node
heappush(self.__heap,node)
def__getitem__(self,key):
ifnotself.__dict.has_key(key):
raiseCacheKeyError(key)
else:
node=self.__dict[key]
#updatenodeobjectin-place
node.atime=time.time()
node._sort_key=self._sort_key()
heapify(self.__heap)
returnnode.obj
def__delitem__(self,key):
ifnotself.__dict.has_key(key):
raiseCacheKeyError(key)
else:
node=self.__dict[key]
delself.__dict[key]
self.__heap.remove(node)
heapify(self.__heap)
returnnode.obj
def__iter__(self):
copy=self.__heap[:]
whilelen(copy)>0:
node=heappop(copy)
yieldnode.key
raiseStopIteration
def__setattr__(self,name,value):
object.__setattr__(self,name,value)
#automagicallyshrinkheaponresize
ifname=='size':
whilelen(self.__heap)>value:
lru=heappop(self.__heap)
delself.__dict[lru.key]
def__repr__(self):
return"<%s(%delements)>"%(str(self.__class__),len(self.__heap))
defmtime(self,key):
"""Returnthelastmodificationtimeforthecacherecordwithkey.
Maybeusefulforcacheinstanceswherethestoredvaluescanget
'stale',suchascachingfileornetworkresourcecontents."""
ifnotself.__dict.has_key(key):
raiseCacheKeyError(key)
else:
node=self.__dict[key]
returnnode.mtime
if__name__=="__main__":
cache=LRUCache(25)
printcache
foriinrange(50):
cache[i]=str(i)
printcache
if46incache:
print"46incache"
delcache[46]
printcache
cache.size=10
printcache
cache[46]='46'
printcache
printlen(cache)
forcincache:
printc
printcache
printcache.mtime(46)
forcincache:
printc
希望本文所述对大家的Python程序设计有所帮助。