473,544 Members | 1,594 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

LRU cache?

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
5 2724
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
Aug 11 '07 #2
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
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
Aug 12 '07 #4
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
Aug 12 '07 #5
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.
Aug 13 '07 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
2835
by: martin | last post by:
Hi, I am storing a dataset in cache, which is happening fine. I can easily retrive it at postback from the cache, cast it to a dataset and reuse it. However I have specified that the cache expire in 5 minutes like so. If Not IsPostBack Then BindMyDropDown() Else Response.Write("<hr>Cache Expires 5 minutes" &
5
1729
by: Darrel | last post by:
I thought this warranted a new thread. Yesterday I asked about access relatively static content...is it better to read from the DB, or just grab a text file. It was suggested that I use the DB and look into the Application Cache settings. I found a good article here: http://www.developer.com/net/net/article.php/1477771
14
2076
by: Tom.PesterDELETETHISSS | last post by:
Hi, I think this question requires an in depth understanding of how a browser cache works. I hope I can reach an expert here. I may have found a quirk in the asp.net documentation or I don't understand what the SetAllowResponseInBrowserHistory does. While researching caching I tried the code sample at the following page : ...
1
2692
by: William Sullivan | last post by:
I'm trying to nail down some issues with the cache in my application. Currently, I have an object that stands between my business logic and database logic called CacheLogic (cute, no?). Global.asax.cs creates it in Application_Start, initializes it and places it in the cache. During initialization, CacheLogic retrieves data from the DB logic...
13
2322
by: Andrew Morton | last post by:
I am caching some data in VB.NET using System.Web.Caching, is it possible to lock the cache so that other sessions attempting to access the same cache wait when it is being updated? I have the cache using a sliding timeout and a dependency on the text file its data is extracted from. If it's relevant, based on current statistics, I do not...
26
6212
by: Ed L. | last post by:
Here's some of my current notions on pgsql performance tuning strictly as it relates to pgsql tuning parameters in the context of a dedicated linux or hpux server. I'm particularly focusing on the shared_buffers setting. I invite any corrective or confirming feedback. I realize there are many other hugely important performance factors...
18
9125
by: siddharthkhare | last post by:
Hi All, what is the diference between these two cache control header. no-cache and no-store. I have read the w3.org explanation. So lets say I am using only no-cache ....my understanding is that nothing is cached and nothing is writen to disk.
0
2285
by: mateipuiu | last post by:
When a try to run a client build on 2005, which uses the Microsoft.ApplicationBlocks.Cache.dll reference, when using a Microsoft.ApplicationBlocks.Cache.dll created on Debug mode, the client works just fine, but when a use a Microsoft.ApplicationBlocks.Cache.dll created on Release mode, the client doesn't work no more, and I get this error...
5
2106
by: Stan SR | last post by:
Hi, Some newbie questions.. :-) First, what is the namespace to use for the Cache class ? When I use this bit of code I get an error if (Cache==null) Cache.Insert("myUserList",userlist); I don't know which namespace to use.
0
1969
by: =?Utf-8?B?YmlqYXk=?= | last post by:
The type initializer for 'Microsoft.ApplicationBlocks.Cache.CacheService' threw an exception. We migrated our windows application from 1.1 to 2.0. The debug and Release mode of the application work fine with some tweaking. But when the setup project is migrated to 2.0 the installation gives the follwing error: - <ExceptionInformation>...
0
7365
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
7607
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
0
7772
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
1
7376
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
7709
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
4918
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3415
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
0
3409
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
0
661
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.