OrderedDict and LRU

Using an OrderedDict lends itself to a LRU cache in very few lines.

from collections import OrderedDict

class LRU(OrderedDict):
    def __init__(self, limit, *args, **kwargs):
        self.limit = limit
        super(LRU, self).__init__(*args, **kwargs)

    def __setitem__(self, key, value):
        if key in self:
            self.move_to_end(key)
        super(LRU, self).__setitem__(key, value)
        if len(self) > self.limit:
            self.popitem(last=False)

    def __getitem__(self, key):
        if key not in self:
            raise KeyError("Key not found {}".format(key))
        self.move_to_end(key)
        return super(LRU, self).__getitem__(key)

Setting and accessing items in a LRU cache:

simon@X220:~$ python3
Python 3.4.0 (default, Apr 11 2014, 13:05:11)
[GCC 4.8.2] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from example import LRU
>>> cache = LRU(limit=3)
>>> cache['a'] = 'Aberdeen'
>>> cache['b'] = 'Bury'
>>> cache['c'] = 'Cardiff'
>>> cache['d'] = 'Derby'
>>> cache['e'] = 'Edinburgh'
>>> cache['f'] = 'Falmouth'
>>> for x in range(3):
...     print(cache.popitem(last=False))
...
('d', 'Derby')
('e', 'Edinburgh')
('f', 'Falmouth')
>>>
>>> cache = LRU(limit=3)
>>> cache['a'] = 'Aberdeen'
>>> cache['b'] = 'Bury'
>>> cache['c'] = 'Cardiff'
>>> print(cache['a'])
Aberdeen
>>> for x in range(3):
...     print(cache.popitem(last=False))
...
('b', 'Bury')
('c', 'Cardiff')
('a', 'Aberdeen')

This is a simple example but demonstrates if you are implementing a LRU cache, you can utilise OrderedDict as the base for your implementation.

Comments !

blogroll

social