By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
444,089 Members | 2,159 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 444,089 IT Pros & Developers. It's quick & easy.

LRU cache?

P: n/a
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.
Aug 11 '07 #1
Share this Question
Share on Google+
5 Replies


P: n/a
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*********@jabber.i-pobox.net
GPG: 0xF534E231
Aug 11 '07 #2

P: n/a
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 +1 571 484 6266 +1 800 494 3119
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 -------------

Aug 11 '07 #3

P: n/a
Paul Rubin <http://ph****@NOSPAM.invalidwrote:
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
Aug 12 '07 #4

P: n/a
In article <7x***************@ruckus.brouhaha.com>,
Paul Rubin <http://ph****@NOSPAM.invalidwrote:
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
Aug 12 '07 #5

P: n/a
Nikita the Spider <Ni*************@gmail.comwrites:
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.
Aug 13 '07 #6

This discussion thread is closed

Replies have been disabled for this discussion.