Python datatype suitable for my cache

Question

I'm searching for the a datatype for a cache, basically I need the functionality of a dict, i.e. random access based on a key, which has a limited number of entries so that when the limit is reached the oldest item gets automatically removed. Furthermore I need to be able to store it via shelve or pickle and rely on Python 2.4. Should I subclass dict and add a list to it? Any suggestions?

Edit:
I have not mentioned the scale, I need to keep track of already read items which consist of a signature by which they are identified and I only want to keep track of about a few hundred of them. collections.deque seem nice but that's a list and I need random access. So dict would seem suitable, however somehow I need to expire items if the limit is hit which means I need to keep track the order in which they have been added.

Answer 1

I think you answered the question yourself. You need to subclass a dict. And you also of course needs to have a list of the keys, so when the list gets too long you can purge the oldest one.

I would however possibly look into memcached or similar.

Answer 2

You probably want an LRU cache (one where "oldest" is measured by "least recently accessed" as opposed to "least recently obtained") -- for most access patterns it performs MUCH better than a naive "oldest goes first" cache (an extremely popular item may easily be the oldest one obtained, but half the recent hits go to it -- how silly to evict it just because it was obtained a long time ago, when it's SO popular!-). Read up on caching in general at wikipedia.

LRU is tricky to program in solid and well-performing ways; I recommend you download, install and reuse lrucache instead. If it doesn't match all of your needs exactly, it's easier to tweak existing code than to start from scratch on a tricky subject.