Welcome, guest | Sign In | My Account | Store | Cart

Good demonstration of inheriting python default object types. Define a maximum size (items, not bytes) to limit to and use as a normal dictionary (be careful to have KeyError exception handling, or use the dictionary's get method with a default value).

Python, 65 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import time

class SizedDict(dict):
    ''' Sized dictionary without timeout. '''

    def __init__(self, size=1000):
        dict.__init__(self)
        self._maxsize = size
        self._stack = []

    def __setitem__(self, name, value):
        if len(self._stack) >= self._maxsize:
            self.__delitem__(self._stack[0])
            del self._stack[0]
        self._stack.append(name)
        return dict.__setitem__(self, name, value)

    # Recommended but not required:
    def get(self, name, default=None, do_set=False):
        try:
            return self.__getitem__(name)
        except KeyError:
            if default is not None:
                if do_set:
                    self.__setitem__(name, default)
                return default
            else:
                raise

class CacheDict(dict):
    ''' A sized dictionary with a timeout (seconds) '''

    def __init__(self, size=1000, timeout=None):
        dict.__init__(self)
        self._maxsize = size
        self._stack = []
        self._timeout = timeout

    def __setitem__(self, name, value, timeout=None):
        if len(self._stack) >= self._maxsize:
            self.__delitem__(self._stack[0])
            del self._stack[0]
        if timeout is None:
            timeout = self._timeout
        if timeout is not None:
            timeout = time.time() + timeout
        self._stack.append(name)
        dict.__setitem__(self, name, (value, timeout))

    def get(self, name, default=None):
        try:
            focus = self.__getitem__(name)
            if focus[1] is not None:
                if focus[1] < time.time():
                    self.__delitem__(name)
                    self._stack.remove(name)
                    raise KeyError
            return focus[0]
        except KeyError:
            return default

#sample usage:
# d = SizedDict()
# for i in xrange(10000): d[i] = 'test'
# print len(d)

This can be used for caching of data where the amount of data cached really matters. Hosting servers, for instance, can impose ram usage limitations, and where you'd really like to store all the information in memory, sometimes you just can't, but you can certainly compromise. Just replace with a regular dict object when you have the memory to burn.

EDIT: Added the CacheDict class. I decided I needed a quick in-memory cache for when I didn't have mcached interfaces available, and added this to a project I'm working on. Figured it compliments the SizedDict class well.

3 comments

Ales Stibal 12 years, 7 months ago  # | flag

Hello! There is a bug, which results in raised KeyError each time you modify existing object in the dict and wait long enough the cache is full. Your __setitem__ simply appends key to the _stack, even when key is already present, which results in duplicate _stacked keys.

William McVey 11 years, 2 months ago  # | flag

Also, you're popping elements off of the front of stack lists. This is documented as being very inefficient in python (basically, requiring all other members of the list to shift down). For performing push/pop operations on both sides of stack, the deque module would be better to use.

iceardor+activestate 10 years ago  # | flag

Using a priority queue rather than a queue (confusingly called self._stack), you have another type of dictionary: A dictionary that keeps the most frequently accessed keys. This may be a good tradeoff between cache hits and memory consumption.

Created by James Kassemi on Tue, 27 Jun 2006 (PSF)
Python recipes (4591)
James Kassemi's recipes (4)

Required Modules

Other Information and Tasks