OrderedDict против dict в Python: выбираем правильный инструмент для работы

Иногда вам нужен Python словарь, который запоминает порядок своих элементов. Раньше был только один инструмент для решения этой конкретной проблемы: Python OrderedDict. Это подкласс словаря, специально разработанный для запоминания порядка элементов, который определяется порядком вставки ключей.

Всё изменилось в Python 3.6. Встроенный класс dict теперь также сохраняет порядок своих элементов. Из-за этого многие в сообществе Python теперь задаются вопросом, полезен ли по-прежнему OrderedDict. Более пристальный взгляд на OrderedDict обнаружит, что этот класс по-прежнему предоставляет ценные функции.

В этом руководстве вы узнаете, как:

• Создавать использовать OrderedDict объекты в своём коде;
• Определите различия между OrderedDict и dict;
• Понять плюсы и минусы использования OrderedDict по сравнению с dict .

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

В завершении руководства вы увидите пример реализации очереди на основе словаря с использованием OrderedDict, что было бы более сложно, если использовался обычный объект dict.

Выбор между OrderedDictи dict

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

Ещё в 2008 году PEP 372 представил идею добавления нового класса словаря в контейнерных типах данных. Его основная цель состояла в том, чтобы запомнить порядок элементов, определяемый порядком вставки ключей. Так появился OrderedDict.

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

OrderedDict был добавлен в стандартную библиотеку Python 3.1. Его API практически такой же, как у dict. Однако OrderedDict перебирает ключи и значения в том же порядке, в котором производилась вставка ключей. Если новая запись перезаписывает существующую запись, то порядок элементов остается неизменным. Если запись удалена и вставлена повторно, она будет перемещена в конец словаря.

Python 3.6 представил новую реализацию dict. Эта новая реализация представляет собой большой выигрыш с точки зрения использования памяти и эффективности итераций. Кроме того, новая реализация предоставляет новую и несколько неожиданную функцию: объекты dict теперь сохраняют свои элементы в том же порядке, в котором они были представлены. Первоначально эта функция считалась деталью реализации, и в документации не рекомендовалось полагаться на неё.

По словам Раймонда Хеттингера, разработчика ядра Python и соавтора OrderedDict, класс был специально разработан, чтобы упорядочивать его элементы, тогда как новая реализация dict была спроектирована так, чтобы быть компактной и обеспечивать быструю итерацию:

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

Напротив, я дал collections.OrderedDict другой дизайн (позже закодированный на C Эриком Сноу). Основная цель состояла в том, чтобы обеспечить эффективное поддержание порядка даже для серьезных рабочих нагрузок, таких как lru_cache, который часто меняет порядок, не затрагивая лежащий в основе dict. Конструкция OrderedDict намеренно отдает приоритет возможностям упорядочивания за счёт дополнительных накладных расходов на память и постоянного фактора худшего времени вставки.

Моя цель по-прежнему заключается в том, чтобы collections.OrderedDict имел другую конструкцию с другими характеристиками, чем у обычных моделей. У него есть некоторые методы, специфичные для порядка, которых нет в обычных dict'ах (например, move_to_end() и popitem(), которые эффективно добавляют данные с любого конца). OrderedDict должен хорошо справляться с этими операциями, потому что это то, что отличает его от обычных dict'ов.

В Python 3.7 упорядоченная по элементам функция объектов dict была объявлена официальной частью спецификации языка Python. Таким образом, с этого момента разработчики могут полагаться на dict, когда им нужен словарь, в котором элементы упорядочены.

Здесь возникает вопрос: нужен ли OrderedDict после этой новой реализации dict? Ответ зависит от вашего конкретного варианта использования, а также от того, насколько явным вы хотите быть в своем коде.

На момент написания некоторые особенности OrderedDict всё ещё делали его ценным и отличающимся от обычного dict:

1. Сигнализация намерения: если вы используете OrderedDictвместо dict , тогда ваш код проясняет, что важен порядок элементов в словаре. Вы чётко даёте понять, что вашему коду нужен порядок элементов в базовом словаре или он полагается на него.
2. Контроль над порядком элементов: если вам нужно переставить или переупорядочить элементы в словаре, вы можете использовать .move_to_end() , а также расширенный вариант .popitem() .
3. Проверка на равенство: если ваш код сравнивает словари на предмет равенства, и порядок элементов важен в этом сравнении, то OrderedDict
4. правильный выбор.

Есть как минимум ещё одна причина продолжать использовать OrderedDict в коде: обратная совместимость. Использование обычных объектов dict для сохранения порядка элементов приведет к поломке вашего кода в средах, в которых выполняются версии Python старше 3.6.

Сложно сказать, заменит ли в ближайшее время dict полностью OrderedDict. В настоящее время OrderedDict по-прежнему предлагает интересные и ценные функции, которые вы, возможно, захотите принять во внимание при выборе инструмента для конкретной работы.

Начало работы с Python OrderedDict

OrderedDict Python - это подкласс dict, который сохраняет порядок, в котором пары ключ-значение, обычно известные как элементы, вставляются в словарь. Когда вы перебираете объект OrderedDict, элементы обходятся в исходном порядке. Если вы обновите значение существующего ключа, порядок останется неизменным. Если удалить элемент и снова вставить, этот элемент будет добавлен в конец словаря.

Подкласс dict означает, что он наследует все методы, которые предоставляет обычный словарь. У OrderedDict также есть дополнительные функции, о которых вы узнаете из этого руководства. Однако в этом разделе вы узнаете основы создания и использования объектов OrderedDict в вашем коде.

Создание объектов OrderedDict

В отличие от dict, OrderedDict не является встроенным типом, поэтому первым шагом для создания объектов OrderedDict является импорт класса из collections. Есть несколько способов создания упорядоченных словарей. Большинство из них идентичны тому, как вы создаете обычный объект dict. Например, вы можете создать пустой объект OrderedDict, создав экземпляр класса без аргументов:

>>> from collections import OrderedDict

>>> numbers = OrderedDict()

>>> numbers["one"] = 1
>>> numbers["two"] = 2
>>> numbers["three"] = 3

>>> numbers
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

В этом случае вы сначала импортируете OrderedDict из collections. Затем создаётся пустой упорядоченный словарь, создавая экземпляр OrderedDict без предоставления аргументов конструктору.

Вы можете добавить в словарь пары ключ-значение, указав ключ в квадратных скобках ([]) и присвоив этому ключу значение. Когда вы ссылаетесь на numbers, вы получаете итерацию пар ключ-значение, которая содержит элементы в том же порядке, в котором они были вставлены в словарь.

Вы также можете передать итератор элементов в качестве аргумента конструктору OrderedDict:

>>> from collections import OrderedDict

>>> numbers = OrderedDict([("one", 1), ("two", 2), ("three", 3)])
>>> numbers
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

>>> letters = OrderedDict({("a", 1), ("b", 2), ("c", 3)})
>>> letters
OrderedDict([('c', 3), ('a', 1), ('b', 2)])

При использовании последовательности, такой как list или tuple, порядок элементов в итоговом упорядоченном словаре совпадает с исходным порядком элементов во входной последовательности. Если вы используете множество, как во втором примере выше, то окончательный порядок элементов неизвестен, пока не будет создан OrderedDict.

Если вы используете обычный словарь в качестве инициализатора объекта OrderedDict и используете Python 3.6 или более позднюю версию, вы получите следующее поведение:

Python 3.9.0 (default, Oct  5 2020, 17:52:02)
[GCC 9.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from collections import OrderedDict

>>> numbers = OrderedDict({"one": 1, "two": 2, "three": 3})
>>> numbers
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

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

Python 3.5.10 (default, Jan 25 2021, 13:22:52)
[GCC 9.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.

>>> from collections import OrderedDict

>>> numbers = OrderedDict({"one": 1, "two": 2, "three": 3})
>>> numbers
OrderedDict([('one', 1), ('three', 3), ('two', 2)])

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

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

>>> from collections import OrderedDict

>>> numbers = OrderedDict(one=1, two=2, three=3)
>>> numbers
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

Начиная с Python 3.6, функции сохраняют порядок ключевых аргументов, передаваемых при вызове. Таким образом, порядок элементов в приведенном выше OrderedDict соответствует порядку, в котором передаются ключевые аргументы конструктору. В более ранних версиях Python этот порядок неизвестен.

Наконец, OrderedDict также предоставляет .fromkeys(), который создаёт новый словарь из итерации ключей и устанавливает для всех его значений общее значение:

>>> from collections import OrderedDict

>>> keys = ["one", "two", "three"]
>>> OrderedDict.fromkeys(keys, 0)
OrderedDict([('one', 0), ('two', 0), ('three', 0)])

В этом случае создаётся упорядоченный словарь, используя список ключей в качестве отправной точки. Второй аргумент .fromkeys() предоставляет одно значение для всех элементов в словаре.

Управление элементами в OrderedDict

Поскольку OrderedDict является изменяемой структурой данных, вы можете выполнять операции изменения с её экземплярами. Вы можете вставлять новые элементы, обновлять и удалять существующие элементы и так далее. Если вы вставляете новый элемент в существующий упорядоченный словарь, то этот элемент добавляется в конец словаря:

>>> from collections import OrderedDict

>>> numbers = OrderedDict(one=1, two=2, three=3)
>>> numbers
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

>>> numbers["four"] = 4
>>> numbers
OrderedDict([('one', 1), ('two', 2), ('three', 3), ('four', 4)])

Новый добавленный элемент, ('four', 4), помещается в конец базового словаря, поэтому порядок существующих элементов остается неизменным, а словарь сохраняет порядок вставки.

Если вы удалите элемент из существующего упорядоченного словаря и снова вставите тот же элемент, то новый экземпляр элемента будет помещён в конец словаря:

>>> from collections import OrderedDict
>>> numbers = OrderedDict(one=1, two=2, three=3)

>>> del numbers["one"]
>>> numbers
OrderedDict([('two', 2), ('three', 3)])

>>> numbers["one"] = 1
>>> numbers
OrderedDict([('two', 2), ('three', 3), ('one', 1)])

Если удалить элемент ('one', 1) и вставить новый экземпляр того же элемента, то новый элемент будет добавлен в конец базового словаря.

Если переназначить или обновить значение существующей пары ключ-значение в объекте OrderedDict, то ключ сохраняет свою позицию, но получает новое значение:

>>> from collections import OrderedDict
>>> numbers = OrderedDict(one=1, two=2, three=3)

>>> numbers["one"] = 1.0
>>> numbers
OrderedDict([('one', 1.0), ('two', 2), ('three', 3)])

>>> numbers.update(two=2.0)
>>> numbers
OrderedDict([('one', 1.0), ('two', 2.0), ('three', 3)])

Если обновить значение данного ключа в упорядоченном словаре, то ключ не перемещается, а назначается новое значение на месте. Таким же образом, если используется .update() для изменения значения существующей пары "ключ- значение", то словарь запоминает положение ключа и присваивает ему обновленное значение.

Итерация по OrderedDict

Как и в случае с обычными словарями, можно выполнять итерацию по объекту OrderedDict, используя несколько инструментов и методов. Можно перебирать ключи напрямую или использовать словарные методы, такие как .items(), .keys() и .values():

>>> from collections import OrderedDict
>>> numbers = OrderedDict(one=1, two=2, three=3)

>>> # Перебирать ключи напрямую
>>> for key in numbers:
...     print(key, "->", numbers[key])
...
one -> 1
two -> 2
three -> 3

>>> # Перебирать элементы с помощью .items()
>>> for key, value in numbers.items():
...     print(key, "->", value)
...
one -> 1
two -> 2
three -> 3

>>> # Перебрать ключи с помощью .keys()
>>> for key in numbers.keys():
...     print(key, "->", numbers[key])
...
one -> 1
two -> 2
three -> 3

>>> # Перебирать значения с помощью .values()
>>> for value in numbers.values():
...     print(value)
...
1
2
3

Первый цикл for перебирает ключи numbers напрямую. Остальные три цикла используют словарные методы для перебора элементов, ключей и значений numbers.

Итерация в обратном порядке с reversed()

Ещё одна важная особенность, которую OrderedDict предоставляет после Python 3.5, заключается в том, что её элементы, ключи и значения поддерживают обратную итерацию с использованием reversed(). Эта функция была добавлена в обычные словари в Python 3.8. Итак, если ваш код использует её, то ваша обратная совместимость гораздо более ограничена обычными словарями.

reversed() можно использовать с элементами, ключами и значениями объекта OrderedDict:

>>> from collections import OrderedDict
>>> numbers = OrderedDict(one=1, two=2, three=3)

>>> # Перебирать ключи напрямую в обратном порядке
>>> for key in reversed(numbers):
...     print(key, "->", numbers[key])
...
three -> 3
two -> 2
one -> 1

>>> # Перебирать элементы в обратном порядке
>>> for key, value in reversed(numbers.items()):
...     print(key, "->", value)
...
three -> 3
two -> 2
one -> 1

>>> # Перебирать ключи в обратном порядке
>>> for key in reversed(numbers.keys()):
...     print(key, "->", numbers[key])
...
three -> 3
two -> 2
one -> 1

>>> # Перебирать значения в обратном порядке
>>> for value in reversed(numbers.values()):
...     print(value)
...
3
2
1

Каждый цикл в этом примере использует reversed() для перебора различных элементов упорядоченного словаря в обратном порядке.

Обычные словари также поддерживают обратную итерацию. Однако, если попытаться использовать reversed() с обычным объектом dict в версии Python ниже 3.8, будет получено исключение TypeError:

Python 3.7.9 (default, Jan 14 2021, 11:41:20)
[GCC 9.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.

>>> numbers = dict(one=1, two=2, three=3)

>>> for key in reversed(numbers):
...     print(key)
...
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'dict' object is not reversible

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

Изучение уникальных возможностей Python OrderedDict

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

Упорядоченный словарь предоставляет доступ к следующим дополнительным и расширенным методам:

• .move_to_end()
• это новый метод, добавленный в Python 3.2, который позволяет переместить существующий элемент в конец или в начало словаря.
• .popitem()
• это расширенный вариант своего аналога dict.popitem() , который позволяет удалять и возвращать элемент либо из конца, либо из начала базового упорядоченного словаря.

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

Наконец, экземпляры OrderedDict предоставляют атрибут с именем .dict, который нельзя найти в обычном экземпляре словаря. Этот атрибут позволяет добавлять настраиваемые атрибуты с возможностью записи в существующий упорядоченный словарь.

Переупорядочивание элементов с помощью .move_to_end()

Одно из наиболее заметных различий между dict и OrderedDict заключается в том, что последний имеет дополнительный метод под названием .move_to_end(). Этот метод позволяет перемещать существующие элементы либо в конец, либо в начало базового словаря, поэтому это отличный инструмент для изменения порядка словаря.

Когда вы используете .move_to_end(), вы можете указать два аргумента:

1. keyсодержит ключ, который идентифицирует элемент, который вы хотите переместить. Если keyне существует, будет поднято KeyError .
2. last содержит логическое значение, определяющее, в какой конец словаря нужно переместить данный элемент. По умолчанию используется значение True , что означает, что элемент будет перемещён в конец или правую часть словаря. False означает, что элемент будет перемещён в начало или в левую часть заказанного словаря.

Вот пример того, как использовать .move_to_end() с аргументом key и полагаться на значение по умолчанию last:

>>> from collections import OrderedDict
>>> numbers = OrderedDict(one=1, two=2, three=3)
>>> numbers
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

>>> numbers.move_to_end("one")
>>> numbers
OrderedDict([('two', 2), ('three', 3), ('one', 1)])

Когда вызывается .move_to_end() с key в качестве аргумента, то производится перемещение имеющейся пары ключ-значение в конец словаря. Поэтому на последнем месте сейчас ('one', 1). Обратите внимание, что остальные элементы остаются в том же первоначальном порядке.

Если установить False в last, производится перемещение элемента в начало:

>>> numbers.move_to_end("one", last=False)
>>> numbers
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

В этом случае ('one', 1) перемещается в начало словаря. Это даёт интересную и мощную функцию. Например, с помощью .move_to_end() можно отсортировать упорядоченный словарь по ключам:

>>> from collections import OrderedDict
>>> letters = OrderedDict(b=2, d=4, a=1, c=3)

>>> for key in sorted(letters):
...     letters.move_to_end(key)
...
>>> letters
OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 4)])

В этом примере сначала создаётся упорядоченный словарь letters. Цикл for перебирает свои отсортированные ключи и перемещает каждый элемент в конец словаря. По окончании цикла элементы упорядоченного словаря отсортированы по ключам.

Сортировка словаря по значениям была бы интересным упражнением.

# Отсортировать следующий словарь по значениям:
>>> from collections import OrderedDict
>>> letters = OrderedDict(a=4, b=3, d=1, c=2)

Вы можете использовать лямбда-функцию для получения букв каждой пары ключ-значение и использовать эту функцию в качестве ключевого аргумента для sorted():

>>> for key, _ in sorted(letters.items(), key=lambda item: item[1]):
...     letters.move_to_end(key)
...
>>> letters
OrderedDict([('d', 1), ('c', 2), ('b', 3), ('a', 4)])

В этом коде используется лямбда-функция, которая возвращает буквы каждой пары "ключ-значение". Вызов sorted() использует эту лямбда-функцию для извлечения ключа сравнения из каждого элемента итерируемого ввода, letter.items(). Затем используется .move_to_end() для сортировки символов.

Удаление элементов с помощью .popitem()

Еще одна интересная особенность OrderedDict - его расширенная версия .popitem(). По умолчанию .popitem() удаляет и возвращает элемент в порядке LIFO (Последний пришёл/первый ушёл). Другими словами, он удаляет элементы из правого конца упорядоченного словаря:

>>> from collections import OrderedDict
>>> numbers = OrderedDict(one=1, two=2, three=3)

>>> numbers.popitem()
('three', 3)
>>> numbers.popitem()
('two', 2)
>>> numbers.popitem()
('one', 1)
>>> numbers.popitem()
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    numbers.popitem()
KeyError: 'dictionary is empty'

Здесь удаляются все элементы из numbers с помощью .popitem(). Каждый вызов этого метода удаляет один элемент из конца базового словаря. Если вызвать .popitem() на пустом словаре, будет получено KeyError. До этого момента .popitem() ведет себя так же, как и в обычных словарях.

Однако в OrderedDict .popitem() также принимает логический аргумент с именем last, который по умолчанию равен True. Если установить last на False, то .popitem() удалит элементы в порядке FIFO (Первым прибыл, первым обслужен), что означает, что он удаляет элементы из начала словаря:

>>> from collections import OrderedDict
>>> numbers = OrderedDict(one=1, two=2, three=3)

>>> numbers.popitem(last=False)
('one', 1)
>>> numbers.popitem(last=False)
('two', 2)
>>> numbers.popitem(last=False)
('three', 3)
>>> numbers.popitem(last=False)
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    numbers.popitem(last=False)
KeyError: 'dictionary is empty'

Если для last задано значение True, можно использовать .popitem() для удаления и возврата элементов из начала упорядоченного словаря. В этом примере последний вызов .popitem() вызывает KeyError, потому что базовый словарь уже пуст.

Проверка на равенство словарей

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

>>> from collections import OrderedDict
>>> letters_0 = OrderedDict(a=1, b=2, c=3, d=4)
>>> letters_1 = OrderedDict(b=2, a=1, c=3, d=4)
>>> letters_2 = OrderedDict(a=1, b=2, c=3, d=4)

>>> letters_0 == letters_1
False

>>> letters_0 == letters_2
True

В этом примере порядок элементов letters_1 немного отличается от порядка элементов letters_0 и letters_2, поэтому первый тест возвращает False. Во втором тесте letters_0 и letters_2 имеют одинаковый набор элементов, которые находятся в одном порядке, поэтому тест возвращает True.

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

>>> letters_0 = dict(a=1, b=2, c=3, d=4)
>>> letters_1 = dict(b=2, a=1, c=3, d=4)
>>> letters_2 = dict(a=1, b=2, c=3, d=4)

>>> letters_0 == letters_1
True

>>> letters_0 == letters_2
True

>>> letters_0 == letters_1 == letters_2
True

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

Наконец, тесты на равенство между объектом OrderedDict и обычным словарем не принимают во внимание порядок элементов:

>>> from collections import OrderedDict
>>> letters_0 = OrderedDict(a=1, b=2, c=3, d=4)
>>> letters_1 = dict(b=2, a=1, c=3, d=4)

>>> letters_0 == letters_1
True

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

Добавление новых атрибутов к экземпляру словаря

У объектов OrderedDict есть атрибут .__dict__, который нельзя найти в обычных объектах словаря. Взгляните на следующий код:

>>> from collections import OrderedDict
>>> letters = OrderedDict(b=2, d=4, a=1, c=3)
>>> letters.__dict__
{}

>>> letters1 = dict(b=2, d=4, a=1, c=3)
>>> letters1.__dict__
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    letters1.__dict__
AttributeError: 'dict' object has no attribute '__dict__'

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

Атрибут .__dict__ упорядоченного словаря можно использовать для хранения динамически создаваемых атрибутов экземпляра с возможностью записи. Есть несколько способов сделать это. Например, можно использовать присвоение в стиле словаря, как в ordered_dict.__dict__["attr"] = value. Можно также использовать точечную нотацию, как в ordered_dict.attr = value.

Вот пример использования .__dict__ для присоединения новой функции к существующему упорядоченному словарю:

>>> from collections import OrderedDict
>>> letters = OrderedDict(b=2, d=4, a=1, c=3)

>>> letters.sorted_keys = lambda: sorted(letters.keys())
>>> vars(letters)
{'sort_keys': <function <lambda> at 0x7fa1e2fe9160>}

>>> letters.sorted_keys()
['a', 'b', 'c', 'd']

>>> letters["e"] = 5
>>> letters.sorted_keys()
['a', 'b', 'c', 'd', 'e']

Теперь у есть функция .sorted_keys() lambda, прикрепленная к упорядоченному словарю letters. Обратите внимание, что можно проверить содержимое .__dict__ либо напрямую, используя точечную нотацию, либо используя vars().

Можно использовать эту динамически добавляемую функцию для перебора ключей словаря в отсортированном порядке без изменения исходного порядка в letters:

>>> for key in letters.sorted_keys():
...     print(key, "->", letters[key])
...
a -> 1
b -> 2
c -> 3
d -> 4
e -> 5

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

Это всего лишь пример того, насколько полезной может быть эта функция OrderedDict. Учтите, что вы не можете сделать что-то подобное с обычным словарем:

>>> letters = dict(b=2, d=4, a=1, c=3)
>>> letters.sorted_keys = lambda: sorted(letters.keys())
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    letters.sorted_keys = lambda: sorted(letters.keys())
AttributeError: 'dict' object has no attribute 'sorted_keys'

Если попытаться динамически добавить настраиваемые атрибуты экземпляра в обычный словарь, то будет получено сообщение AttributeError, сообщающее, что в базовом словаре нет атрибута. Это связано с тем, что в обычных словарях нет атрибута .__dict__ для хранения новых атрибутов экземпляра.

Словарные операторы слияния и обновления

Python 3.9 добавил два новых оператора в словарное пространство. Теперь есть операторы слияния (|) и обновления (|=) словаря. Эти операторы также работают с экземплярами OrderedDict:

Python 3.9.0 (default, Oct  5 2020, 17:52:02)
[GCC 9.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.


>>> from collections import OrderedDict

>>> physicists = OrderedDict(newton="1642-1726", einstein="1879-1955")
>>> biologists = OrderedDict(darwin="1809-1882", mendel="1822-1884")

>>> scientists = physicists | biologists
>>> scientists
OrderedDict([
   ('newton', '1642-1726'),
   ('einstein', '1879-1955'),
   ('darwin', '1809-1882'),
   ('mendel', '1822-1884')
])

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

Оператор обновления удобен, когда у вас есть словарь и вы хотите обновить некоторые из его значений, не вызывая .update():

>>> physicists = OrderedDict(newton="1642-1726", einstein="1879-1955")

>>> physicists_1 = OrderedDict(newton="1642-1726/1727", hawking="1942-2018")
>>> physicists |= physicists_1
>>> physicists
OrderedDict([
    ('newton', '1642-1726/1727'),
    ('einstein', '1879-1955'),
    ('hawking', '1942-2018')
])

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

Учитывая производительность

Производительность - важная тема в программировании. Знание того, насколько быстро работает алгоритм или сколько памяти он использует, - это общие проблемы. OrderedDict изначально был написан на Python, а затем написан на C, чтобы максимизировать эффективность его методов и операций. Эти две реализации в настоящее время доступны в стандартной библиотеке. Однако реализация Python служит альтернативой, если реализация C по какой-либо причине недоступна.

Обе реализации OrderedDict предполагают использование двусвязного списка для определения порядка элементов. Несмотря на наличие линейного времени для некоторых операций, реализация связанного списка в OrderedDict сильно оптимизирована для сохранения быстрого времени соответствующих методов словаря. Тем не менее, операции с упорядоченным словарем равны O(1), но с большим постоянным коэффициентом по сравнению с обычными словарями.

В целом у OrderedDict более низкая производительность, чем у обычных словарей. Вот пример, который измеряет время выполнения нескольких операций над обоими классами словарей:

# time_testing.py

from collections import OrderedDict
from time import perf_counter

def average_time(dictionary):
    time_measurements = []
    for _ in range(1_000_000):
        start = perf_counter()
        dictionary["key"] = "value"
        "key" in dictionary
        "missing_key" in dictionary
        dictionary["key"]
        del dictionary["key"]
        end = perf_counter()
        time_measurements.append(end - start)
    return sum(time_measurements) / len(time_measurements) # int(1e9)

ordereddict_time = average_time(OrderedDict.fromkeys(range(1000)))
dict_time = average_time(dict.fromkeys(range(1000)))
gain = ordereddict_time / dict_time

print(f"OrderedDict: {ordereddict_time:.2f} ns")
print(f"dict:        {dict_time:.2f} ns ({gain:.2f}x faster)")

В этом сценарии вычисляется average_time(), необходимое для выполнения нескольких общих операций с данным словарем. Цикл for использует time.pref_counter() для измерения времени выполнения набора операций. Функция возвращает среднее время в наносекундах, которое требуется для выполнения выбранного набора операций.

Если запустить этот сценарий из командной строки, то получите примерно такой результат:

$ python time_testing.py
OrderedDict: 272.93 ns
dict:        197.88 ns (1.38x faster)

Как видно из выходных данных, операции с объектами dict выполняются быстрее, чем операции с объектами OrderedDict.

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

>>> import sys
>>> from collections import OrderedDict

>>> ordereddict_memory = sys.getsizeof(OrderedDict.fromkeys(range(1000)))
>>> dict_memory = sys.getsizeof(dict.fromkeys(range(1000)))
>>> gain = 100 - dict_memory / ordereddict_memory `` 100

>>> print(f"OrderedDict: {ordereddict_memory} bytes")
OrderedDict: 85408 bytes

>>> print(f"dict:        {dict_memory} bytes ({gain:.2f}% lower)")
dict:        36960 bytes (56.73% lower)

В этом примере используется sys.getsizeof() для измерения объёма памяти в байтах для двух объектов словаря. В выходных данных вы можете видеть, что обычный словарь занимает меньше памяти, чем его аналог OrderedDict.

Выбор подходящего словаря для работы

До сих пор вы узнали о тонких различиях между OrderedDict и dict. Вы узнали, что, несмотря на то, что обычные словари были упорядоченными структурами данных, начиная с Python 3.6, использование OrderedDict всё же имеет некоторую ценность из-за набора полезных функций, которых нет в dict.

Вот краткое изложение наиболее важных различий и функций обоих классов, которые следует учитывать при их выборе:

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

Создание очереди на основе словаря

Вариант использования, в котором следует рассмотреть возможность использования объекта OrderedDict, а не объекта dict, - это когда необходимо реализовать очередь на основе словаря. Очереди - это общие и полезные структуры данных, которые управляют своими элементами по принципу FIFO. Это означает, что новые элементы добавляются в конец очереди, а старые элементы выходят из начала очереди.

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

Чтобы создать очередь на основе словаря, запустите свой редактор кода или IDE, создайте новый модуль Python с именем queue.py и добавьте в него следующий код:

# queue.py

from collections import OrderedDict

class Queue:
    def __init__(self, initial_data=None, /, ``*kwargs):
        self.data = OrderedDict()
        if initial_data is not None:
            self.data.update(initial_data)
        if kwargs:
            self.data.update(kwargs)

    def enqueue(self, item):
        key, value = item
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value

    def dequeue(self):
        try:
            return self.data.popitem(last=False)
        except KeyError:
            print("Empty queue")

    def __len__(self):
        return len(self.data)

    def __repr__(self):
        return f"Queue({self.data.items()})"

В Queue сначала инициализируется атрибут экземпляра с именем .data. Этот атрибут содержит пустой упорядоченный словарь, который будет использоваться для хранения данных. Инициализатор класса принимает первый необязательный аргумент, initial_data, который позволяет вам предоставить начальные данные при создании экземпляра класса. Инициализатор также принимает необязательные аргументы ключевого слова (kwargs), чтобы вы могли использовать аргументы ключевого слова в конструкторе.

Затем кодируется .enqueue(), что позволяет добавлять пары ключ-значение в очередь. В этом случае используется .move_to_end(), если ключ уже существует, и используется обычное назначение для новых ключей. Обратите внимание, что для того, чтобы этот метод работал, вам необходимо предоставить двухэлементный tuple или list с действительной парой ключ-значение.

Реализация .dequeue() использует .popitem() с last, установленным на False, для удаления и возврата элементов из начала базового упорядоченного словаря .data. В этом случае используется блок try … except для обработки KeyError, который возникает, когда вы вызывается .popitem() на пустом словаре.

Специальный метод .len() обеспечивает необходимую функциональность для получения длины внутреннего упорядоченного словаря .data. Наконец, специальный метод .__repr__() обеспечивает удобное строковое представление очереди при печати структуры данных на экране.

Вот несколько примеров использования Queue:

>>> from queue import Queue

>>> # Создание пустой очереди
>>> empty_queue = Queue()
>>> empty_queue
Queue(odict_items([]))

>>> # Создание очереди с исходными данными
>>> numbers_queue = Queue([("one", 1), ("two", 2)])
>>> numbers_queue
Queue(odict_items([('one', 1), ('two', 2)]))

>>> # Создание очереди с ключевыми аргументами
>>> letters_queue = Queue(a=1, b=2, c=3)
>>> letters_queue
Queue(odict_items([('a', 1), ('b', 2), ('c', 3)]))

>>> # Добавление элементов
>>> numbers_queue.enqueue(("three", 3))
>>> numbers_queue
Queue(odict_items([('one', 1), ('two', 2), ('three', 3)]))

>>> # Удаление элементов
>>> numbers_queue.dequeue()
('one', 1)
>>> numbers_queue.dequeue()
('two', 2)
>>> numbers_queue.dequeue()
('three', 3)
>>> numbers_queue.dequeue()
Empty queue

В этом примере кода сначала создаётся три разных объекта Queue, используя разные подходы. Затем используется .enqueue(), чтобы добавить один элемент в конец numbers_queue. Наконец, несколько раз вызывается .dequeue(), чтобы удалить все элементы в numbers_queue. Обратите внимание, что последний вызов .dequeue() выводит на экран сообщение о том, что очередь уже пуста.

Выводы

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

Python 3.6 представил новую функцию в обычных словарях. Теперь они также запоминают порядок элементов. С этим дополнением большинство программистов Python задаются вопросом, нужно ли им все еще рассматривать возможность использования OrderedDict.

В этом уроке вы узнали:

• Как создавать и использовать объекты OrderedDictв вашем коде;
• В чем основные различия между OrderedDictи dict;
• Какие плюсы и минусы использования OrderedDictпо сравнению с dict .

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

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