Simple lru cache?

[Bengt Richter]

On Sat, 05 Oct 2002 14:54:57 +0200, Ype Kingma <ykingma at accessforall.nl> wrote:

>Guido Goldstein schreef:
>
>> 
>> Hi!
>> 
>> On Fri, 04 Oct 2002 22:52:06 +0200
>>   Ype Kingma <ykingma at accessforall.nl> wrote:
>>> Hello,
>>> 
>>> Does anyone know of a good lru cache implementation in python?
>>> I tried google, and found some things in zope, but these are
>>> more complicated than what I need.
>> 
>> You might have a look at
>>   http://www.a-nugget.org/downloads/LRUCache.py
>> 
>> It's a time based lru-cache with manual or automatic shrink.
>> I think it's commented enough to get a rough understanding of how it
>> works.
>> 
>> Of course, comments and suggestions are welcome.
>
>
>In my first attempt with the doubly linked list I store a doubly linked
>list element together with the user data. Such an element can be
>removed quite easily from the (lru) list it is in, after which
>it can be inserted in front. Also the final element can be removed
>when the cache fills up. For this the key needs to be stored in
>the doubly linked list element.
>
>You store a timestamp together with the user data in a dictionary so
>shrinking can be based on age. Such shrinking needs an extra effort
>periodically but it's probably more efficient.
>
I also did a doubly linked list. It should be general purpose enough
for you to try it easily. The linked list part may be very similar to
yours? I used a circular list of nodes with data and a key. The key
is used in a dictionary that finds a node with that key and corresponding
data. The key can be used to delete the dictionary reference when the LRU
node gets reused. The cache object has a getValue(*args) method and
it uses a calcValue(*args) function you supply to calculate a value (or
get it from dbm, whatever). The value is stored in a list node, and
the *args tuple is used as a key (unless you supply a hashCalc function,
in which case that is called with *args to generate a key) to map from
args->node to get the value from the node later.



Regards,
Bengt Richter