Simple lru cache?
bokr at oz.net
Sun Oct 6 07:42:35 CEST 2002
On Sat, 05 Oct 2002 14:54:57 +0200, Ype Kingma <ykingma at accessforall.nl> wrote:
>Guido Goldstein schreef:
>> On Fri, 04 Oct 2002 22:52:06 +0200
>> Ype Kingma <ykingma at accessforall.nl> wrote:
>>> 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
>> 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
>> 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.
More information about the Python-list