Блог

Я рассматривал решение для реализации кэша LRU в leetcode. И встроенный dict также упорядочен из Python 3.6 . Мне было интересно, есть ли какая-либо функция, похожая на move_to_end() OrderedDict, которую я могу использовать со встроенным dict и избавиться от OrderedDict.

 from collections import OrderedDict
class LRUCache(OrderedDict):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self:
            return - 1
        
        self.move_to_end(key)
        return self[key]

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last = False)
 

Лучшее, что вы можете сделать, это удалить запись и вставить ее заново:

 d[key] = d.pop(key)
 

Обратите внимание, что не существует эффективного способа переместить запись в начало OrderedDict , поддерживаемое способом, из-за различий в том, как реализуется сохранение порядка.