removing the oldest element from a dictionary in python

Question

I would like to know the best way to remove the oldest element in a dictionary in order to control the maximum dictionary size.

example:

MAXSIZE = 4
dict = {}
def add(key,value):
  if len(dict) == MAXSIZE:
    old = get_oldest_key() # returns the key to the oldest item
    del dict[old]
  dict[key] = value

add('a','1') # {'a': '1'}
add('b','2') # {'a': '1', 'b': '2'}
add('c','3') # {'a': '1', 'c': '3', 'b': '2'}
add('d','4') # {'a': '1', 'c': '3', 'b': '2', 'd': '4'}
add('e','5') # {'c': '3', 'b': '2', 'e': '5', 'd': '4'}

Was this clear? Thanks in advance.

edit forgot that len(dict) lags one item behind

Answer 1

Dictionaries don't preserve order, so you can't tell which element had been added first. You could combine the dictionary with a list of it's keys to preserve order.

Here's an activestate recipe for an ordered dict that does just this.

There's also PEP-0372 with this patch for an odict class.

Answer 2

Unless you had some kind of set number of elements, where you know which one is the oldest, then you could simply delete it. Otherwise, you're using the wrong data structure for what you're doing I think.

EDIT: Though, according to a quick google, I've come across this. Oh I do like the collections module :)

Answer 3

One way to do this would be to store the keys in an array, which will preserve your order for you. Something like:

MAXSIZE = 4
dict = {}
history = []
def add(key,value):
    print len(dict)
    if len(dict) == MAXSIZE:
        old = history.pop(0) # returns the key to the oldest item
        del dict[old]
    history.append(key)
    dict[key] = value

Also, keep in mind that len() will always lag one item behind. When you are adding your fifth item, len(dict) is 4, not 5. You should use == instead of >.

Answer 4

Python 3.1 has an ordered dict. use the class collections.OrderedDict to keep the elements in their order of insertions. beware that if you are overwriting an element, it keeps its place in the order, you need to delete and re-insert an element to make it last.

if you are using an older release, a patch may be available to get OrderedDict.

anyway, if it is not available, you may simply use a list of tuples: it can be easily converted to and from a dictionary, keeps its ordering, can be used like a queue with append and pop, ...

Answer 5

Without knowing what you're really trying to use this structure for, here's something that may work for you:

class DictCache:
    def __init__(self, maxcount=4):
        self.data = {}
        self.lru = []
        self.maxcount = maxcount
    def add(self, key, value):
        self.data[key] = value
        self.lru.append(key)
        if len(self.lru) > self.maxcount:
            dead = self.lru.pop(0)
            del(self.data[dead])

Combine this with a get method that rearranges self.lru when they are accessed, and you can change your caching strategy to suit your usecase.

Answer 6

Alternatively a list of tuples could be used for this as well.

MAXSIZE = 4
stack = []

def add(key, value):
 stack.append((key, value))
 if len(stack) > MAXSIZE:
  stack.pop(0)

 print stack

add('a','1')
add('b','2')
add('c','3')
add('d','4')
add('e','5')

results in

[('a', '1')]
[('a', '1'), ('b', '2')]
[('a', '1'), ('b', '2'), ('c', '3')]
[('a', '1'), ('b', '2'), ('c', '3'), ('d', '4')]
[('b', '2'), ('c', '3'), ('d', '4'), ('e', '5')]

Note you do loose the speed of a dictionary lookup with this method. So if you need that a custom ordered dictionary may be in order.

You can find a implementation by the pocoo team here. I've always found their work to be excellent.

Answer 7

how about like this? put order in array and when its reach limit, pop it.

MAXSIZE = 4
dict,order= {},[]

def add(key,value):
    if len(dict) > MAXSIZE:
     old = order.pop() # returns the key to the oldest item
     del dict[old]
    order.insert(0,key)
    dict[key] = value

Answer 8

I believe LRU dict-like container will suite your needs the best.