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

Перевод статьи OrderedDict vs dict in Python: The Right Tool for the Job.

Время от времени в наших проектах на Python возникает необходимость структурировать данные в виде словаря, в котором гарантировано должен сохраняться порядок следования его элементов. И ранее у нас был только один инструмент для решения этой проблемы – использование класса OrderedDict, предоставляемого модулем collections. Этот класс упорядоченного словаря, специально разработан для запоминания и сохранения порядка размещения его элементов (пар ключ-значение), который свою очередь определяется последовательностью их вставки.

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

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

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

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

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

Нелегкий выбор между OrderedDict и dict

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

Еще в 2008 году стандарт PEP 372 представил вниманию разработчиков идею добавления нового класса словаря, добавленного в модуль collections. Его основная цель состояла в том, чтобы запоминать порядок следования элементов (ключей), определяемый порядком, в котором они были вставлены в объект класса. Этот принцип был положен в основу реализации и использования нового класса OrderedDict.

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

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

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

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

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

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

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

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

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

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

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

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

OrderedDict это класс словаря, который сохраняет порядок, в котором пары ключ-значение, известные как элементы (items), были вставлены в словарь. И если вы осуществляете перебор элементов в объекте OrderedDict, то они следуют друг другом каждый раз в строго определенном порядке. При этом если вы обновите значение существующего ключа, то порядок, в котором расположены элементы останется неизменным. Если вы удалите элемент, а затем его снова вставите в словарь, то он будет добавлен в его конец.

Так как OrderedDict по сути является отдельным классом, то это означает, что кроме методов, которые предоставляет обычный словарь, словарь 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)])

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

Если вы используете обычный словарь dict для инициализации нового объекта класса 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 представляют собой изменяемую структуру данных, то вы можете выполнять различные операции (mutating) с элементами его экземпляров. Вы можете вставлять новые элементы или удалять существующие, обновлять их значения и так далее. Если же вы вставляете новый элемент в существующий упорядоченный словарь, то он будет добавлен в конец:

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

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

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

>>> # Итерация с использованием метода values() по списку значений в обратном порядке
>>> 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 "", line 1, in 
TypeError: 'dict' object is not reversible

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

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

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

• .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:

>>> 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) будет располагаться на последней позиции. Обратите внимание, что остальные элементы остаются в первоначальном порядке.

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

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

Такая техника использования этого метода предоставляет новую интересную возможность. Например, следующим образом с помощью метода 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 перебираем отсортированные ключи и каждый раз перемещаем текущий элемент в конец словаря. По окончании цикла элементы упорядоченного словаря будут сортированы по именам ключей.

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

Рассмотрим еще одну интересную возможность использования OrderedDict – это расширенная версия метода popitem. По умолчанию метод popitem удаляет и возвращает элементы последовательности в порядке LIFO (Last-In / First-Out). Другими словами, он удаляет и возвращает элементы из правого конца упорядоченного словаря:

>>> 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 "", line 1, in 
    numbers.popitem()
KeyError: 'dictionary is empty'

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

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

>>> 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 "", line 1, in 
    numbers.popitem(last=False)
KeyError: 'dictionary is empty'

Сравниваем словари

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

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

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

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

В примере выше словарь letter_1 отличается порядком элементов по сравнению с letter_0 и letter_2, поэтому первый тест возвращает False. Во втором тесте так как letter_0 и letter_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 "", line 1, in 
    letters1.__dict__
AttributeError: 'dict' object has no attribute '__dict__'

В первом примере мы получаем доступ к атрибуту __ dict__ упорядоченного словаря letters. Python может использовать этот атрибут для хранения доступных для перезаписи атрибутов (свойств) текущего экземпляра класса. Второй пример показывает, что у обычных объектов словаря такого атрибута нет.

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

Существует несколько способов это делать. Например, вы можете присваивать атрибуту значения в стиле обычного словаря, например, так order_dict .__ dict __ ["attr"] = value. Или же используя точечную нотацию – order_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)
{'sorted_keys':  at 0x7fa1e2fe9160>}

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

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

Как видим теперь лямбда-функция sorted_keys прикреплена к объекту упорядоченного словаря letters. Обратите внимание, что вы можете проверить содержимое атрибуту __ dict__ непосредственно используя точечную нотацию, либо функцию vars().

Примечательно, что этот динамический атрибут добавляется к конкретному экземпляру класса. В приведенном выше примере это объект letters. Изменение атрибута ни как не влияет на другие экземпляры, ни на сам класс, поэтому у вас есть доступ к функции sorted_keys() только через ссылку на конкретный объект letters.

Вы можете использовать эту динамически добавляемую функцию для перебора ключей словаря в сортированном порядке, не изменяя исходный порядок элементов словаря 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 "", line 1, in 
    letters.sorted_keys = lambda: sorted(letters.keys())
AttributeError: 'dict' object has no attribute 'sorted_keys'

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

Используем операторы объединения merging и обновления updating словарей

В версии Python 3.9 было добавлено два новых оператора для работы со словарями. И теперь мы можем пользоваться операторами merging объединения (слияния) | и обновления updating |= словарей. Эти операторы также корректно работают с экземплярами класса 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. Во втором словаре, который предоставляет собой обновленные данные, есть также новый ключ hawking со значением. В результате выполнения кода видим, что новая пара ключ-значение hawking="1942-2018" добавлена в конец исходного словаря.

Анализ производительности

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

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

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

Таким образом, обработка элементов объекта класса 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
Обеспечение порядка вставки ключей	Да (начиная с Python 3.1)	Да (начиная с Python 3.6)
Удобочитаемость кода и обозначение намерений относительно порядка элементов	Высокая	Низкая
Контроль за порядком элементов	Высокий ( move_to_end(), усилен popitem())	Низкий (требуется удаление и повторная вставка элементов)
Производительность операций	Низкая	Высокая
Потребление памяти	Высокое	Низкое
Тесты на эквивалентность учитывают порядок элементов	Да	Нет
Поддержка возможности итерации в обратном направлении	Да (начиная с Python 3.5)	Да (начиная с Python 3.8)
Возможность добавлять новые атрибуты экземпляра класса	Да ( атрибут __dict__)	Нет
Поддержка операторов объединения merge ( |) и обновленя update ( |=) словарей	Да (начиная с Python 3.9)	Да (начиная с Python 3.9)

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

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

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

Как правило для работы с очередью необходимо реализовать следующие операции. Операцию вставки элемента в конец очереди, которая более известна как enqueue (постановка в очередь). А также удаления элементов с ее начала, более известная как dequeue (выталкивание из очереди).

Для начала создадим новый скрипт 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. В случае возникновения исключительной ситуации, если метод popitem будет вызван для пустого словаря, используется блок try…except для обработки соответствующего исключения типа KeyError.

Специальный метод __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 все еще может на что-то пригодиться.