1

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.

  • Please decide whether you want to discard the entry that was updated last (most recent) or the entry with the oldest update (least recent). Hint: discarding the most recent will result in the same 999 entries remaining in the dictionary forever. – A. I. Breveleri Mar 18 '15 at 3:47
  • @A.I.Breveleri Sorry for the confusion. That wasn't indecision. Rather, I was clarifying what I meant by "updated last," but I see now that it's confusing. I've corrected the mistake. – sinθ Mar 19 '15 at 20:01
  • 1
    You are looking for a stack. Keep pushing recently updated items into stack. You will pop from stack to get recent items. When ever you update an item, remove its existing entry and push it on top of stack. This can be implemented as discussed using LinkedHashMap in java. I don't have knowledge of Python. – TechCrunch Mar 19 '15 at 20:12
  • Can you please confirm that what you need is not an LRU cache? Python has that built-in – Basilevs Apr 19 '15 at 12:16
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.

0

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.

  • Appreciate the answer, but I don't think it works. Let's say the maximum is three and I inserted pair A first. Then I inserted pair B. Then I inserted pair C. Then I updated the value of A. last_changed would now be: ACBA. When I insert pair D, A gets removed, even though it was updated most recently. – sinθ Mar 20 '15 at 0:05
  • Ah, I see. I misunderstood what you were trying to do. In that case, you would need a dictionary based on time, which means a dictionary lookup on every insert. – Gort the Robot Mar 20 '15 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.