How to remove the oldest element from a dictionary

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?

Edit: Forgot that len(dict) lags one item behind.

Answer 1

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

Answer 2

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 3

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 4

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 5

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 6

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 :)