Implementing a cache

Nikolaus Rath Nikolaus at
Fri Jul 10 15:22:29 CEST 2009


I want to implement a caching data structure in Python that allows me

 1. Quickly look up objects using a key
 2. Keep track of the order in which the objects are accessed (most
    recently and least recently accessed one, not a complete history)
 3. Quickly retrieve and remove the least recently accessed object.

Here's my idea for the implementation:

The objects in the cache are encapsulated in wrapper objects:

class OrderedDictElement(object):
    __slots__ = [ "next", "prev", "key", "value" ]

These wrapper objects are then kept in a linked lists and in an ordinary
dict ( in parallel. Object access then works as follows:

    def __setitem__(self, key, value):
        if key in
            # Key already exists, just overwrite value
  [key].value = value
            # New key, attach at head of list
            with self.lock:
                el = OrderedDictElement(key, value,, prev=self.head)
       = el
       = el
      [key] = el

    def __getitem__(self, key):
To 'update the access time' of an object, I use
    def to_head(self, key):
        with self.lock:
            el =[key]
            # Splice out
   = el.prev
            # Insert back at front
            el.prev = self.head
   = el
   = el

self.head and self.tail are special sentinel objects that only have a
.next and .prev attribute respectively.

While this is probably going to work, I'm not sure if its the best
solution, so I'd appreciate any comments. Can it be done more elegantly?
Or is there an entirely different way to construct the data structure
that also fulfills my requirements?

I already looked at the new OrderedDict class in Python 3.1, but
apparently it does not allow me to change the ordering and is therefore
not suitable for my purpose. (I can move something to one end by
deleting and reinserting it, but I'd like to keep at least the option of also
moving objects to the opposite end).



 »Time flies like an arrow, fruit flies like a Banana.«

  PGP fingerprint: 5B93 61F8 4EA2 E279 ABF6  02CF A9AD B7F8 AE4E 425C

More information about the Python-list mailing list