Limiting the size of a python dictionary

Question

I'd like to work with a dict in python, but limit the number of key/value pairs to X. In other words, if the dict is currently storing X key/value pairs and I perform an insertion, I would like one of the existing pairs to be dropped. It would be nice if it was the least recently inserted/accesses key but that's not completely necessary.

If this exists in the standard library please save me some time and point it out!

Answer 1

You can create a custom dictionary class by subclassing dict. In your case, you would have to override __setitem__ to have check your own length and delete something if the limit is recahed. The following example would print the current lenght after every insertion:

class mydict(dict):
    def __setitem__(self, k, v):
        dict.__setitem__(self, k, v)
        print len(self)

d = mydict()
d['foo'] = 'bar'
d['bar'] = 'baz'

Answer 2

A dict does not have this behavior. You could make your own class that does this, for example something like

class MaxSizeDict(object):
    def __init__(self, max_size):
        self.max_size = max_size
        self.dict = {}
    def __setitem__(self, key, value):
        if key in self.dict:
            self.dict[key] = value    
            return

        if len(self.dict) >= self.max_size:
      ...

A few notes about this

• It would be tempting for some to subclass dict here. You can technically do this, but it is bug-prone because the methods do not depend on each other. You can use UserDict.DictMixin to save having to define all methods. There are few methods you would be able re-use if you subclass dict.
• A dict does not know what the least recently added key is, since dicts are unordered.
  • 2.7 will introduce collections.OrderedDict, but for now keeping the keys in order separately should work fine (use a collections.deque as a queue).
  • If getting the oldest isn't all that imporant, you can just use the popitem method to delete one arbitrary item.
• I interprettered oldest to mean first insertion, approximately. You would have to do something a bit different to eliminate the LRU items. The most obvious efficient strategy would involve keeping a doubly-linked list of keys with references to the nodes themselves stored as dict values (along with the real values). This gets more complicated and implementing it in pure Python carries a lot of overhead.

Answer 3

Python 2.7 and 3.1 have OrderedDict and there are pure-Python implementations for earlier Pythons.

class LimitedSizeDict(OrderedDict):
  def __init__(self, *args, **kwds):
    self.size_limit = kwds.pop("size_limit", None)
    OrderedDict.__init__(self, *args, **kwds)
    self._check_size_limit()

  def __setitem__(self, key, value):
    OrderedDict.__setitem__(self, key, value)
    self._check_size_limit()

  def _check_size_limit(self):
    if self.size_limit is not None:
      while len(self) > self.size_limit:
        self.popitem(last=False)

You would also have to override other methods that can insert items, such as update. The primary use of OrderedDict is so you can control what gets popped easily, otherwise a normal dict would work.

Answer 4

Here's a simple, no-LRU Python 2.6+ solution (in older Pythons you could do something similar with UserDict.DictMixin, but in 2.6 and better that's not recommended, and the ABCs from collections are preferable anyway...):

import collections

class MyDict(collections.MutableMapping):
  def __init__(self, maxlen, *a, **k):
    self.maxlen = maxlen
    self.d = dict(*a, **k)
    while len(self) > maxlen:
      self.popitem()
  def __iter__(self):
    return iter(self.d)
  def __len__(self):
    return len(self.d)
  def __getitem__(self, k):
    return self.d[k]
  def __delitem__(self, k):
    del self.d[k]
  def __setitem__(self, k, v):
    if k not in self and len(self) == self.maxlen:
      self.popitem()
    self.d[k] = v 

d = MyDict(5)
for i in range(10):
  d[i] = i
  print sorted(d)

As other answers mentioned, you probably don't want to subclass dict -- the explicit delegation to self.d is unfortunately boilerplatey but it does guarantee that every other method is properly supplied by collections.MutableDict.