Simple lru cache?

[Ype Kingma]

Bjorn Pettersen schreef:

>> From: Ype Kingma [mailto:ykingma at accessforall.nl]
>> 
>> Does anyone know of a good lru cache implementation in
>> python?
> 
> Perhaps http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117228
> will give you some ideas?

This is a priorityDictionary. Quoting from the page:

Description:

This data structure acts almost like a dictionary, with two modifications: 
First, D.smallest() returns the value x minimizing D[x]. For this to work 
correctly, all values D[x] stored in the dictionary must be comparable. 
Second, iterating "for x in D" finds and removes the items from D in sorted 
order. Each item is not removed until the next item is requested, so D[x] 
will still return a useful value until the next iteration of the for-loop.

End of quote.

I don't see immediately how the aging needed for least recently used
could be implemented using a priorityDictionary. It's use of binary heaps
might help to overcome the problem with of age gaps in the suggestion
Alex Martelli made.

> And also perhaps:
> http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/python/python/dist/src/Li
> b/heapq.py?rev=HEAD&content-type=text/vnd.viewcvs-markup

A heapq library. From the url it looks like this is meant to be included
in the next python distribution. More batteries, good news.

Thanks,
Ype