Efficient datastructure to create size-limited dictionary

Question

I need a class that acts like a dictionary but will constrain the total number of key/value pairs it contains. For instance, let's say the maximum number of entries is 1000 and the class already contains 1000 key/value pairs. If I add an additional key/value pair, the class should remove the key-value pair that was updated least recently.

Here's my current implementation in python:

class SizeLimitedDefaultDict(defaultdict):
    last_changed = []

    def __init__(self, default, max_size, *args, **kwargs):
        max_size = 0
        super(SizeLimitedDict, self).__init__(default, *args, **kwargs)

    def __setitem__(self, key, val):
        if len(self) >= self.max_size:
            remove_oldest_entry()
        super.__setitem__(self, key, val)
        update_newest_entry(key)

    def update_newest_entry(self, key):
        key_index = last_changed.index(key) #will slow it down
        last_changed.insert(0, last_changed.pop(key_index))

This clearly isn't a viable solution. All the performance gains of the dictionary are lost. I'm having trouble figuring out a better solution though. Is there a data structure that can easily maintain which keys have been most recently updated.

Answer 1

You should store the keys in two structures simultaneously -- a tree (or heap), and a doubly-linked list. Each node of the tree must include a pointer to the corresponding entry in the linked list. The values should be stored with the tree nodes; the list entries need only the keys.

To look up a value, the linked list need not be consulted or altered.

To update a key/value pair, find it in the tree and overwrite its value. Then use its list pointer to identify the corresponding list entry. Unlink the entry from its current location and link it to the end of the list. This action maintains the list in update order.

To identify the least recently updated entry, simply read the key from the first item in the linked list.

I think you know the rest. Look up that node in the tree, overwrite its key and value, and move it to its proper place in the tree, but without altering its list pointer. Also overwrite the key in the list entry, and don't neglect to unlink it and move it to the end of the list.

Answer 2

Use a queue to manage the keys by recency:

from collections import deque

class SizeLimitedDefaultDict(defaultdict):
    last_changed = deque()

    def __setitem__(self, key, val):
        if len(self) >= self.max_size:
            del self[last_changed.popleft()]

        super.__setitem__(self, key, val)
        last_changed.append(key)

Roughly speaking, when the dictionary gets "full", you'll pay for one dictionary lookup for every insert.