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

This is a mapping-like object that attempts to efficiently hold a fixed number of previous entries, automatically discarding older entries.

Python, 48 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
# This could much more completely be done as a subclass of dict, but for
# brevity we'll just define it like this for now.

class FifoCache:
    '''
    A mapping(ish) object that remembers the past <entries> items set.
    '''

    def __init__(self, entries):
        self.entries = entries

        self.dct = {}
        self.lst = []

        self.__repr__ = self.dct.__repr__
        self.__contains__ = self.dct.__contains__
        self.__getitem__ = self.dct.__getitem__


    def __setitem__(self, key, value):
        dct = self.dct
        lst = self.lst

        if key in self:
            del self[key]

        lst.append(key)
        dct[key] = value

        if len(lst) > self.entries:
            del dct[lst.pop(0)]


    def __delitem__(self, key):
        if not self.dct.has_key(key):
            raise KeyError, key

        self.lst.remove(key)
        self.dct.pop(key)


# f = FifoCache(entries = 3)
# f["fly"] = "foo"
# f["moo"] = "two"
# f["bar"] = "baz"
# f["dave"] = "wilson"
# f["age"] = 20
# f now has keys 'bar', 'dave', and 'age'.

For any case where you might use a dictionary object to cache expensive lookups, this might be a safer alternative for use in long-running applications, who's caches may consume all system memory if left unchecked.

The one problem with this implementation is that it is not a full dictionary; you cannot safely replace dict() with FifoCache(), since FifoCache has not got the same methods as dict. It does however support item getting, setting, and __contains__, which should be adequate for 50%+ uses.

At a little cost to speed for the wrapped methods, this could be rewritten properly as a subclass of the dict type, providing drop-in compatibility, which would make for an excellent tool in an optimiser's toolset.

2 comments

Raymond Hettinger 17 years, 7 months ago  # | flag

Full Dictionary Interface. An easy way to expand the interface is to subclass from UserDict.DictMixin in Py2.3.

Josiah Carlson 17 years, 3 months ago  # | flag

Similar recipe... I will point to a similar recipe here:

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

It uses LRU and offers a fairly complete dictionary interface.

Created by David Wilson on Sun, 4 Apr 2004 (PSF)
Python recipes (4591)
David Wilson's recipes (1)
Python Cookbook Edition 2 (117)

Required Modules

  • (none specified)

Other Information and Tasks