Как удалить самый старый элемент из словаря?

Question

Я хотел бы знать, как лучше всего удалить самый старый элемент в словаре, чтобы контролировать максимальный размер словаря.

Пример

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'}

Было ли это ясно?

Редактировать: Забыл, что len(dict) отстает от одного элемента.

Answer 1

Python 3.1 имеет упорядоченный dict. используйте класс collections.OrderedDict, чтобы сохранить элементы в порядке их вставки. помните, что если вы перезаписываете элемент, он сохраняет свое место в порядке, вам нужно удалить и заново вставить элемент, чтобы сделать его последним.

если вы используете более старую версию, может быть доступно исправление для получения OrderedDict.

в любом случае, если он недоступен, вы можете просто использовать список кортежей: его можно легко преобразовать в словарь и из словаря, сохранить его порядок, можно использовать как очередь с append и pop, ...

Answer 2

Словари не сохраняют порядок, поэтому вы не можете сказать, какой элемент был добавлен первым. Вы можете объединить словарь со списком его ключей, чтобы сохранить порядок.

Вот рецепт activestate для упорядоченного дикта, который делает именно это.

Существует также PEP-0372 с этим патчем для класса odict.

Answer 3

Полагаю, LRU, похожий на диктовку контейнер удовлетворит ваши потребности наилучшим образом.

Answer 4

Один из способов сделать это - сохранить ключи в массиве, который сохранит ваш заказ для вас. Что-то вроде:

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

Кроме того, имейте в виду, что len() всегда будет отставать от одного элемента. Когда вы добавляете пятый элемент, len(dict) равен 4, а не 5. Вы должны использовать == вместо >.

Answer 5

Если у вас не было какого-то определенного количества элементов, где вы знаете, какой из них самый старый, вы можете просто удалить его. В противном случае вы используете неправильную структуру данных для того, что вы делаете, я думаю.

РЕДАКТИРОВАТЬ : Хотя, согласно быстрому гуглу, я встречал это. О, мне нравится модуль collections :)

Answer 6

В качестве альтернативы для этого можно использовать список кортежей.

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

результаты в

[('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')]

Обратите внимание, что при этом методе вы теряете скорость поиска в словаре. Так что, если вам нужно, заказанный словарь может быть в порядке.

Вы можете найти реализацию команды pocoo здесь . Я всегда находил их работу превосходной.

Answer 7

как насчет этого? выставить порядок в массиве и когда достигнет предела, вытолкнуть его.

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

Не зная, для чего вы действительно пытаетесь использовать эту структуру, вот то, что может работать для вас:

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

Объедините это с get методом, который переставляет self.lru когда к ним обращаются, и вы можете изменить свою стратегию кэширования в соответствии с UseCase.