Optimize a cache

[Florian Lindner]

Hello,
I am building a object cache in python, The cache has a maximum size and the
items have expiration dates.
At the moment I'm doing like that:

cache = {} # create dictionary

cache[ID] = (object, timestamp) # Save a tuple with the object itself and a
timestamp (from datetime.datetime.now()) under a unique object ID. This
make looking up a certain item a cheap operation (AFAIK). After looking up
my program checks if the expiration date and returns cache[ID][1] or
retrieve a new object and overwrite the one saved in the cache.

My problem now:
When len(cache) > cacheSize I need to remove the oldest objects (the ones
with the smalest timestamp). For that I need to iterate through all items
and get the oldest one: (pseudo code)

oldest = datetime.datetime.now()

for i in cache:
if i[1] < a:
id = i
n = i[0]

del cache[id]


What possible you see to optimize this lookup? Or anything else you see to
make it better?

Thanks,

Florian

 

[Paul Rubin]

What possible you see to optimize this lookup? Or anything else you see to
make it better?

Use the heapq module.

 

[gene tani]

i think ring buffer

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/68429

 

[Paul Rubin]

What possible you see to optimize this lookup? Or anything else you see to
make it better?

Do you need to update the timestamp of cached entries when you access
them? If yes, use the heapq module. If no, is the cache something
different from a simple FIFO?

 

[gene tani]

a ring buffer?

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/68429

 

[Tim Williams]

----- Original Message -----

Hello,
I am building a object cache in python, The cache has a maximum size and the
items have expiration dates.
At the moment I'm doing like that:

What possible you see to optimize this lookup? Or anything else you see to
make it better?

Have a look at http://py.vaults.ca/apyllo.py/514463245.769244789.92554878
it already has some of your requirements, and can be used as a building
block.