Re: LRU cache?
- From: qyloxe@xxxxxxxxx
- Date: Mon, 20 Aug 2007 05:10:01 -0700
#simple, but effective (sometimes)
class ICORCache:
def __init__(self,agetfunc,amaxlen=100):
self.GetValue=agetfunc
self.MaxLen=amaxlen
self.VDict={}
self.KDict={}
self.VPos=1
self.AccessRatio=0
self.HitRatio=0
def __getitem__(self,key):
self.AccessRatio=self.AccessRatio+1
id=self.KDict.get(key,0)
if id:
self.HitRatio=self.HitRatio+1
return self.VDict[id][1]
else:
v=self.VDict.get(self.VPos,0)
if v:
del self.KDict[v[0]]
ret=apply(self.GetValue,(key,))
self.VDict[self.VPos]=[key,ret]
self.KDict[key]=self.VPos
self.VPos=self.VPos+1
if self.VPos>self.MaxLen:
self.VPos=1
return ret
def dump(self):
print 'Access ratio:',self.AccessRatio
print 'Hit ratio:',self.HitRatio
print 'Hit %:',100.0*self.HitRatio/self.AccessRatio
print 'VDict len:',len(self.VDict.keys())
print 'KDict len:',len(self.KDict.keys())
#tests
if __name__=='__main__':
import random
def GetCalculatedValue(key):
x=`key`+'aaaa'
y=key*0.5
z=x+`y`
return z
# model of distribution
amax=1000
def GetIterative(key):
return key
def GetRandom(key):
return random.randint(1,amax)
l1,l2,l3=random.randint(1,amax),random.randint(1,amax),random.randint(1,amax)
def GetNDist(key):
global l1,l2,l3
l1,l2,l3=l2,l3,random.randint(1,amax)
return int((l1+l2+l3)/3)
def Main():
for aname,afunc in [['Iterative',GetIterative],
['Random',GetRandom],['NDist',GetNDist]]:
acache=ICORCache(GetCalculatedValue,100)
for i in range(1000):
k=afunc(i)
x=acache[k]
y=GetCalculatedValue(k)
if x!=y:
print 'Error!!!',k,x,y
print 'Name:',aname
acache.dump()
return
Main()
.
- References:
- LRU cache?
- From: Paul Rubin
- LRU cache?
- Prev by Date: datetime in microseconds
- Next by Date: Shed Skin Python-to-C++ compiler 0.0.23
- Previous by thread: Re: LRU cache?
- Next by thread: Metaclass v.s. Property function.
- Index(es):
Relevant Pages
|
