|
Упорядоченный словарь OrderedDictКурс по стандартной библиотеке: https://stepik.org/a/259466?utm_source=proproprogs До версии языка Python 3.7 словари (dict) могли быть не упорядоченными, то есть, порядковое расположение ключей в словаре могло отличаться от указанного в программе. Например, словарь: d = {'a': 1, 'b': 2, 'c': 3, 'd': 4} при последовательном выводе пар ключ-значение: for k, v in d.items(): print(f"{k}: {v}") вполне мог выдать следующий порядок: b:
2
Однако, начиная с версии Python 3.7, словари dict стали гарантированно упорядоченными, что было закреплено на уровне стандарта этого языка. Это значит, что порядок следования ключей в словаре совпадает с порядком их добавления в него. В нашем примере словарь d будет выдавать ключи строго от ‘a’ до ‘d’: a: 1
И никак иначе. Но еще до появления упорядоченных словарей dict в ряде задач требовался строго определенный порядок следования ключей. И для этих целей был разработан класс OrderedDict на базе стандартного класса dict: class OrderedDict(dict): 'Dictionary that remembers insertion order' ... который расположен в модуле collections. Казалось бы, после появления упорядоченности в стандартных словарях Python, необходимость в классе OrderedDict отпала? Однако не все так просто. Остаются ситуации, когда OrderedDict имеет смысл применять. Например:
К тому же на сегодняшний день существует множество реализованных алгоритмов, использующих словарь OrderedDict. А потому важно понимать принцип его работы. Создание словарей OrderedDictВ самом простом варианте словарь OrderedDict можно создать командой: from collections import OrderedDict od = OrderedDict() Получим пустой словарь. И, так как он наследует функционал базового класса dict, то добавлять и изменять новые пары ключ-значение можно следующим образом: od['a'] = 0 # создание пары 'a' => 0 od['b'] = 2 od['d'] = 3 od['c'] = 4 od['a'] = 1 # изменение значения ключа 'a' print(od) # OrderedDict([('a', 1), ('b', 2), ('d', 3), ('c', 4)]) Порядок их следования будет гарантирован. Если же нужно создать не пустой словарь OrderedDict, то достаточно передать любую итерируемую последовательность в виде вложенных пар ключ-значений: od1 = OrderedDict([('key1', 1), ('key2', 'hello'), ('key3', True)]) od2 = OrderedDict((['key1', 1], ['key2', 'hello'], ['key3', True])) od3 = OrderedDict(zip(['val1', 'val2', 'val3'], [1, 2, 3])) Пары ключ-значение, при их явном определении, рекомендуется записывать в виде кортежей. Операции сравнения словарей OrderedDictСловари OrderedDict поддерживают все те же самые операции сравнения, что и обычные словари dict. Однако при определении равенства или неравенства в OrderedDict дополнительно проверяется порядок следования ключей. Например, для двух обычных словарей типа dict: d1 = {'a': 1, 'b': 2, 'c': 3} d2 = {'b': 2, 'a': 1, 'c': 3} операция сравнения на равенство: d1 == d2 # True вернет значение True. Но для аналогичных словарей OrderedDict: od1 = OrderedDict([('a', 1), ('b', 2), ('c', 3)]) od2 = OrderedDict([('b', 2), ('a', 1), ('c', 3)]) Эта же операция вернет значение False: od1 == od2 # False По аналогии работает и противоположная операция «!=» сравнения на неравенство. Методы move_to_end() и popitem()Класс OrderedDict содержит дополнительный метод move_to_end(), который перемещает указанный ключ в конец или начало словаря. Например, если для словаря: od1 = OrderedDict([('key1', 1), ('key2', 'hello'), ('key3', True)]) вызвать метод: od1.move_to_end('key2') то ключ 'key2' со своим значением окажется в конце: print(od1) # OrderedDict([('key1', 1), ('key3', True), ('key2', 'hello')]) А если дополнительно указать параметр last=False: od1.move_to_end('key2') od1.move_to_end('key3', last=False) print(od1) # OrderedDict([('key3', True), ('key1', 1), ('key2', 'hello')]) то указанный ключ переместится в начало словаря. Другой весьма полезный метод popitem() класса OrderedDict позволяет удалять первую или последнюю пару ключ-значение, возвращая ее. Например: od1 = OrderedDict([('key1', 1), ('key2', 'hello'), ('key3', True)]) print(od1.popitem()) # ('key3', True) print(od1.popitem(last=False)) # ('key1', 1) Напомню, что аналогичный метод обычного словаря dict позволяет удалять только последнюю пару ключ-значение: d = {'a': 1, 'b': 2, 'c': 3, 'd': 4} print(d.popitem()) # ('d', 4) Пример реализации LRU-кэша на базе словаря OrderedDictКак видите, словарь OrderedDict несколько отличается своим функционалом от обычного словаря dict. И в ряде задач эти отличия играют важную роль. Например, в качестве простой демонстрации, реализуем LRU-кеширование (Least Recently Used caching), используя OrderedDict. Кэш будет реализован в виде отдельного класса LRUCache, унаследованный от базового класса OrderedDict с указанием в инициализаторе объема кэша capacity (максимального количества записей): class LRUCache(OrderedDict): def __init__(self, capacity): super().__init__() self.capacity = capacity def get(self, key): if key not in self: return None else: self.move_to_end(key, last=False) # Перемещаем использованный ключ в начало return self[key] def put(self, key, value): if len(self) >= self.capacity: self.popitem() # удаляем самую последнюю (старую) запись self[key] = value # добавляем новую запись self.move_to_end(key, last=False) # перемещаем ее в начало В самом классе добавлены два метода get() и put(). Метод get() возвращает запись из кэша по указанному ключу. Если он присутствует в словаре, то возвращается его значение, а сам ключ перемещается в начало. Таким образом, последние использованные записи будут размещены в начале словаря, а наименее используемые – в конце. Второй метод put() добавляет в словарь новую запись (пару ключ-значение) и перемещает ее в начало. И, кроме того, осуществляет проверку на общий размер записей. Если их больше или равно заданному значению capacity, то удаляется наиболее старая (наименее используемая). Так реализуется LRU-кэш. Воспользоваться классом LRUCache можно следующим образом: cache = LRUCache(3) data = [('data-1', 1), ('data-2', 'abc'), ('data-3', [1, 2, 3]), ('data-4', True)] for k, v in data: cache.put(k, v) print(cache) # LRUCache([('data-4', True), ('data-3', [1, 2, 3]), ('data-2', 'abc')]) d = cache.get('data-2') print(cache) # LRUCache([('data-2', 'abc'), ('data-4', True), ('data-3', [1, 2, 3])]) Вначале задается размер кэша в 3 элемента (записи), затем идет набор данных data и все они по порядку помещаются в кэш. Первый элемент с ключом 'data-1' оказывается отброшенным, т.к. не помещается в кэш. Далее, читаются данные по ключу 'data-2' и эта запись перемещается в начало словаря. Как видите, словарь OrderedDict имеет свои особенности работы и несколько отличается от обычного словаря dict. Конечно, для большинства задач словаря dict вполне достаточно, но иногда имеет смысл посмотреть и в сторону словаря OrderedDict. Курс по стандартной библиотеке: https://stepik.org/a/259466?utm_source=proproprogs Видео по теме |
