LRU cache?

[Paul Rubin]

Anyone got a favorite LRU cache implementation? I see a few in google
but none look all that good. I just want a dictionary indexed by
strings, that remembers the last few thousand entries I put in it.

It actually looks like this is almost a FAQ. A well-written
implementation would probably make a good standard library module.

[Thomas Wittek]

Paul Rubin schrieb:

Anyone got a favorite LRU cache implementation? I see a few in google
but none look all that good. I just want a dictionary indexed by
strings, that remembers the last few thousand entries I put in it.

I don't know a module for that (although it might exist), but I could
imagine how to implement it.

Generally a LRU cache could be implemented as a (linked) list with a
max. size of N.
On usage of an object this object will be moved to the top of the list
(and removed from the old position).
If it's not yet stored in the cache, you (fetch it from the source and)
add it on top and remove the last one, if the list exceeds N entries.

So you need to do two things:
1) Maintain a list: Use a (linked) list.
2) Random access to that list: Use a dict (hash), that also has to be
updated on removal/addition of objects.

--
Thomas Wittek
Web: http://gedankenkonstrukt.de/
Jabber: st*********@jab ber.i-pobox.net
GPG: 0xF534E231

[Steve Holden]

Thomas Wittek wrote:

Paul Rubin schrieb:

>Anyone got a favorite LRU cache implementation? I see a few in google
but none look all that good. I just want a dictionary indexed by
strings, that remembers the last few thousand entries I put in it.

I don't know a module for that (although it might exist), but I could
imagine how to implement it.

Generally a LRU cache could be implemented as a (linked) list with a
max. size of N.
On usage of an object this object will be moved to the top of the list
(and removed from the old position).
If it's not yet stored in the cache, you (fetch it from the source and)
add it on top and remove the last one, if the list exceeds N entries.

So you need to do two things:
1) Maintain a list: Use a (linked) list.
2) Random access to that list: Use a dict (hash), that also has to be
updated on removal/addition of objects.

Paul's an old enough hand that he's well able to determine this for
himself. He's also polite enough not to reply along those lines :-)

*I* don't know of module for tracking how plants grow, but I could
imagine how to implement it ...

regards
Steve
--
Steve Holden [phone] [phone]
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://del.icio.us/steve.holden
--------------- Asciimercial ------------------
Get on the web: Blog, lens and tag the Internet
Many services currently offer free registration
----------- Thank You for Reading -------------

[Alex Martelli]

Paul Rubin <http://ph****@NOSPAM.i nvalidwrote:

Anyone got a favorite LRU cache implementation? I see a few in google
but none look all that good. I just want a dictionary indexed by
strings, that remembers the last few thousand entries I put in it.

So what's wrong with Evan Prodromou's lrucache.py module that's in pypi?
Haven't used it, but can't see anything wrong at a glance.
Alex

[Nikita the Spider]

In article <7x************ ***@ruckus.brou haha.com>,
Paul Rubin <http://ph****@NOSPAM.i nvalidwrote:

Anyone got a favorite LRU cache implementation? I see a few in google
but none look all that good. I just want a dictionary indexed by
strings, that remembers the last few thousand entries I put in it.

It actually looks like this is almost a FAQ. A well-written
implementation would probably make a good standard library module.

This one works for me:
http://www.webfast.com/~skip/python/Cache.py

--
Philip
http://NikitaTheSpider.com/
Whole-site HTML validation, link checking and more

[Paul Rubin]

Nikita the Spider <Ni************ *@gmail.comwrit es:

This one works for me:
http://www.webfast.com/~skip/python/Cache.py

Thanks, this one keeps track of the actual clock time rather than just
the relative age of cache entries, and has kind of a weird ageing
mechanism, building and sorting an O(n) sized list when the cache gets
95% full, giving amortized O(log n) operations per update. But the
license is ok and I guess the functionality I need is there. So I may
use it and/or code something.