Общие структуры данных Python (руководство)

>>> phonebook = {
...     "bob": 7387,
...     "alice": 3719,
...     "jack": 7052,
... }

>>> squares = {x: x * x for x in range(6)}

>>> phonebook["alice"]
3719

>>> squares
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}


Существуют некоторые ограничения на то, какие объекты могут использоваться в качестве допустимых ключей.
 Словари Python индексируются по ключам, которые могут быть любого типа с возможностью хэширования. Хэшируемый объект  имеет   хэш-значение, которое никогда не меняется в течение всего срока его службы (см. __hash__), и его можно сравнить с другими объектами (см. __eq__). Хэшируемые объекты, которые сравниваются как равные, должны иметь одинаковое хэш-значение.
 Неизменяемые типы, такие как строки и  числа можно хэшировать и они хорошо работают как ключи словаря. Вы также можете использовать tuple объекты в качестве ключей словаря, если они сами содержат только хэшируемые типы.
в большинстве случаев, встроенную в Python осуществления словарь будет делать все, что вам нужно. Словари оптимизированы и лежат в основе многих частей языка. Например, class атрибуты и переменные стек оба хранятся в словарях.
 Словари Python основаны на хорошо протестированной и точно настроенной реализации хэш-таблицы, которая обеспечивает ожидаемые характеристики производительности: O(1) временная сложность операций поиска, вставки, обновления и удаления в среднем случае.
Нет особых причин не использовать стандартную реализацию dict, входящую в состав Python. Однако существуют специализированные сторонние реализации словарей, такие как списки пропусков или Словари на основе B-дерева.
Помимо обычных объектов dict, стандартная библиотека Python также включает в себя ряд специализированных реализаций словарей. Все эти специализированные словари основаны на встроенном классе dictionary (и обладают общими характеристиками производительности), но также включают некоторые дополнительные функции удобства.
Давайте взглянем на них.
collections.OrderedDict: Запомните порядок вставки клавиш
В Python есть специализированный dict подкласс, который запоминает порядок вставки добавленных в него ключей: collections.OrderedDict.
 Примечание: OrderedDict не является встроенной частью основного языка и должен быть импортирован из модуля collections стандартной библиотеки.
В то время как стандартные экземпляры dict сохраняют порядок вставки ключей в CPython 3.6 и выше, это было просто побочным эффектом реализации CPython и не было определено в языке спецификации до версии Python 3.7. Итак, если порядок ключей важен для работы вашего алгоритма, то лучше всего четко указать это, явно используя класс OrderedDict:

>>> import collections
>>> d = collections.OrderedDict(one=1, two=2, three=3)

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

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

>>> d.keys()
odict_keys(['one', 'two', 'three', 'four'])


До  версии Python 3.8 вы не могли перебирать элементы словаря в обратном порядке, используя reversed(). Только экземпляры OrderedDict предлагали такую функциональность. Даже в Python 3.8 объекты dict и OrderedDict не совсем одинаковы. Экземпляры OrderedDict имеют .move_to_end() метод, который недоступен в обычном экземпляре dict, а также в более настраиваемом методе .popitem(), чем в одном простом экземпляре dict.
collections.defaultdict: Возвращает значения по умолчанию для отсутствующих ключей
Класс defaultdict - это еще один подкласс словаря, который принимает в своем конструкторе вызываемый объект, возвращаемое значение которого будет использоваться, если запрошенный ключ не может быть найден.
Это сэкономит вам время на ввод текста и сделает ваши намерения более ясными по сравнению с использованием get() или перехватом KeyError исключения в обычных словарях:

>>> from collections import defaultdict
>>> dd = defaultdict(list)

>>> # Accessing a missing key creates it and
>>> # initializes it using the default factory,
>>> # i.e. list() in this example:
>>> dd["dogs"].append("Rufus")
>>> dd["dogs"].append("Kathrin")
>>> dd["dogs"].append("Mr Sniffles")

>>> dd["dogs"]
['Rufus', 'Kathrin', 'Mr Sniffles']


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

>>> from collections import ChainMap
>>> dict1 = {"one": 1, "two": 2}
>>> dict2 = {"three": 3, "four": 4}
>>> chain = ChainMap(dict1, dict2)

>>> chain
ChainMap({'one': 1, 'two': 2}, {'three': 3, 'four': 4})

>>> # ChainMap searches each collection in the chain
>>> # from left to right until it finds the key (or fails):
>>> chain["three"]
3
>>> chain["one"]
1
>>> chain["missing"]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'missing'


types.MappingProxyType: Оболочка для создания словарей, доступных только для чтения
MappingProxyType это оболочка для стандартного словаря, которая предоставляет доступ к данным обернутого словаря только для чтения. Этот класс был добавлен в Python 3.3 и может быть использован для создания неизменяемых прокси-версий словарей.
MappingProxyType может быть полезно, если, например, вы хотите вернуть словарь, содержащий внутреннее состояние, из класса или модуля, в то же время препятствуя доступу на запись к этому объекту. Использование MappingProxyType позволяет ввести эти ограничения без предварительного создания полной копии словаря:

>>> from types import MappingProxyType
>>> writable = {"one": 1, "two": 2}
>>> read_only = MappingProxyType(writable)

>>> # The proxy is read-only:
>>> read_only["one"]
1
>>> read_only["one"] = 23
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'mappingproxy' object does not support item assignment

>>> # Updates to the original are reflected in the proxy:
>>> writable["one"] = 42
>>> read_only
mappingproxy({'one': 42, 'two': 2})


Словари на Python: Краткое описание
Все реализации словаря Python, перечисленные в этом руководстве, являются допустимыми реализациями, встроенными в стандартную библиотеку Python.
Если вы ищете общие рекомендации о том, какой тип отображения использовать в ваших программах, я бы порекомендовал вам встроенный тип данных dict. Это универсальная и оптимизированная реализация хэш-таблицы, которая встроена непосредственно в основной язык.
Я бы рекомендовал вам использовать один из других перечисленных здесь типов данных только в том случае, если у вас есть особые требования, выходящие за рамки того, что предусмотрено dict.
Все реализации являются допустимыми вариантами, но ваш код будет более понятным и простым в обслуживании, если большую часть времени он будет опираться на стандартные словари Python.
Структуры данных массива
Массив  - это фундаментальная структура данных, доступная в большинстве языков программирования, и она имеет широкий спектр применений в различных алгоритмах.
В этом разделе вы познакомитесь с реализациями массивов в Python, которые используют только основные языковые возможности или функциональные возможности, включенные в стандартную библиотеку Python. Вы увидите сильные и слабые стороны каждого подхода, чтобы решить, какая реализация подходит для вашего варианта использования.
Но прежде чем мы перейдем к делу, давайте сначала рассмотрим некоторые основы. Как работают массивы и для чего они используются? Массивы состоят из записей данных фиксированного размера, которые позволяют эффективно определять местоположение каждого элемента на основе его индекса:

Поскольку массивы хранят информацию в смежных блоках памяти, они считаются смежными структурами данных (в отличие от связанных структур данных, таких как связанные списки, например).
Реальной аналогией структуры данных массива является автостоянка. Вы можете рассматривать автостоянку в целом и рассматривать ее как единый объект, но внутри автостоянки есть парковочные места, проиндексированные уникальным номером. Парковочные места представляют собой контейнеры для транспортных средств — каждое парковочное место может быть либо пустым, либо на нем может быть припаркован автомобиль, мотоцикл или какое-либо другое транспортное средство.
Но не все парковки одинаковы. На некоторых парковках может быть разрешено движение только одного типа транспортных средств. Например, на парковке для домов на колесах запрещено парковать велосипеды. Парковка с ограниченным доступом соответствует типизированной структуре данных массива, которая допускает только элементы, хранящиеся в них с одинаковым типом данных.
 С точки зрения производительности, поиск элемента, содержащегося в массиве, по его индексу выполняется очень быстро. Правильная реализация массива гарантирует постоянное значение O(1) в данном случае время доступа.
В стандартную библиотеку Python включено несколько структур данных, похожих на массивы, каждая из которых имеет несколько разные характеристики. Давайте посмотрим.
list: Изменяемые динамические массивы
 Списки являются частью ядра языка Python. Несмотря на свое название, списки в Python реализованы в виде динамических массивов за кулисами.
Это означает, что список позволяет добавлять или удалять элементы, и список автоматически настраивает резервное хранилище, в котором хранятся эти элементы, путем выделения или освобождения памяти.
 Списки Python могут содержать произвольные элементы — в Python все является объектами, включая функции. Таким образом, вы можете смешивать и сопоставлять различные типы данных и хранить их все в одном списке.
Это может быть полезной функцией, но недостатком является то, что поддержка нескольких типов данных одновременно означает, что данные, как правило, менее плотно упакованы. В результате вся структура занимает больше места:

>>> arr = ["one", "two", "three"]
>>> arr[0]
'one'

>>> # Lists have a nice repr:
>>> arr
['one', 'two', 'three']

>>> # Lists are mutable:
>>> arr[1] = "hello"
>>> arr
['one', 'hello', 'three']

>>> del arr[1]
>>> arr
['one', 'three']

>>> # Lists can hold arbitrary data types:
>>> arr.append(23)
>>> arr
['one', 'three', 23]


tuple: Неизменяемые контейнеры
Как и списки, кортежи являются частью основного языка Python. Однако, в отличие от списков, объекты tuple в Python являются неизменяемыми. Это означает, что элементы не могут быть добавлены или удалены динамически — все элементы в кортеже должны быть определены во время создания.
Кортежи - это еще одна структура данных, которая может содержать элементы произвольных типов. Такая гибкость очень важна, но, опять же, это также означает, что данные упакованы менее плотно, чем в типизированном массиве:

>>> arr = ("one", "two", "three")
>>> arr[0]
'one'

>>> # Tuples have a nice repr:
>>> arr
('one', 'two', 'three')

>>> # Tuples are immutable:
>>> arr[1] = "hello"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

>>> del arr[1]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object doesn't support item deletion

>>> # Tuples can hold arbitrary data types:
>>> # (Adding elements creates a copy of the tuple)
>>> arr + (23,)
('one', 'two', 'three', 23)


array.array: Базовые типизированные массивы
 Модуль Python array обеспечивает экономичное хранение базовых типов данных в стиле Си, таких как байты, 32-разрядные целые числа, числа с плавающей запятой и так далее.
Массивы, созданные с помощью класса array.array, являются изменяемыми и ведут себя аналогично спискам, за исключением одного важного отличия: это типизированных массивов, ограниченных одним типом данных.
Из-за этого ограничения array.array объекты с большим количеством элементов занимают больше места, чем списки и кортежи. Хранящиеся в них элементы плотно упакованы, и это может быть полезно, если вам нужно хранить много элементов одного типа.
Кроме того, массивы поддерживают многие из тех же методов, что и обычные списки, и вы могли бы использовать их в качестве дополнительной замены, не требуя внесения других изменений в код вашего приложения:

>>> import array
>>> arr = array.array("f", (1.0, 1.5, 2.0, 2.5))
>>> arr[1]
1.5

>>> # Arrays have a nice repr:
>>> arr
array('f', [1.0, 1.5, 2.0, 2.5])

>>> # Arrays are mutable:
>>> arr[1] = 23.0
>>> arr
array('f', [1.0, 23.0, 2.0, 2.5])

>>> del arr[1]
>>> arr
array('f', [1.0, 2.0, 2.5])

>>> arr.append(42.0)
>>> arr
array('f', [1.0, 2.0, 2.5, 42.0])

>>> # Arrays are "typed":
>>> arr[1] = "hello"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: must be real number, not str


str: Неизменяемые массивы символов Юникода
В Python 3.x используются str объекты для хранения текстовых данных в виде неизменяемых последовательностей  символов Юникода. Практически это означает, что str - это неизменяемый массив символов. Как ни странно, это также рекурсивная структура данных — каждый символ в строке сам по себе является str объектом длиной 1.
Строковые объекты занимают мало места, потому что они плотно упакованы и специализируются на одном типе данных. Если вы храните текст в Юникоде, то вам следует использовать строку. 
Поскольку строки в Python являются неизменяемыми, для изменения строки требуется создать измененную копию. Наиболее близким эквивалентом изменяемой строки является сохранение отдельных символов внутри списка:

>>> arr = "abcd"
>>> arr[1]
'b'

>>> arr
'abcd'

>>> # Strings are immutable:
>>> arr[1] = "e"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

>>> del arr[1]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object doesn't support item deletion

>>> # Strings can be unpacked into a list to
>>> # get a mutable representation:
>>> list("abcd")
['a', 'b', 'c', 'd']
>>> "".join(list("abcd"))
'abcd'

>>> # Strings are recursive data structures:
>>> type("abc")
"<class 'str'>"
>>> type("abc"[0])
"<class 'str'>"


bytes: Неизменяемые массивы из отдельных байтов
bytes объекты представляют собой неизменяемые последовательности из отдельных байтов или целых чисел в диапазоне 0 ≤ x ≤ 255. Концептуально объекты bytes похожи на объекты str, и вы также можете рассматривать их как неизменяемые массивы байт.
Как и строки, bytes имеют свой собственный литеральный синтаксис для создания объектов и экономят пространство. bytes объекты неизменяемы, но, в отличие от строк, существует специальный изменяемый тип данных массива байт, называемый bytearray что они могут быть распакованы в: 

>>> arr = bytes((0, 1, 2, 3))
>>> arr[1]
1

>>> # Bytes literals have their own syntax:
>>> arr
b'\x00\x01\x02\x03'
>>> arr = b"\x00\x01\x02\x03"

>>> # Only valid `bytes` are allowed:
>>> bytes((0, 300))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: bytes must be in range(0, 256)

>>> # Bytes are immutable:
>>> arr[1] = 23
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'bytes' object does not support item assignment

>>> del arr[1]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'bytes' object doesn't support item deletion


bytearray: Изменяемые массивы из отдельных байтов
Тип bytearray - это изменяемая последовательность целых чисел в диапазоне 0 ≤ x ≤ 255. Объект bytearray тесно связан с объектом bytes, с основным отличием в том, что объект bytearray можно свободно изменять — вы можете перезаписывать элементы, удалять существующие или добавлять новые. Объект bytearray будет соответственно увеличиваться и уменьшаться в размерах.
A bytearray может быть преобразован обратно в неизменяемые bytes объекты, но для этого требуется полное копирование сохраненных данных — медленная операция, занимающая O(n) время:

>>> arr = bytearray((0, 1, 2, 3))
>>> arr[1]
1

>>> # The bytearray repr:
>>> arr
bytearray(b'\x00\x01\x02\x03')

>>> # Bytearrays are mutable:
>>> arr[1] = 23
>>> arr
bytearray(b'\x00\x17\x02\x03')

>>> arr[1]
23

>>> # Bytearrays can grow and shrink in size:
>>> del arr[1]
>>> arr
bytearray(b'\x00\x02\x03')

>>> arr.append(42)
>>> arr
bytearray(b'\x00\x02\x03*')

>>> # Bytearrays can only hold `bytes`
>>> # (integers in the range 0 <= x <= 255)
>>> arr[1] = "hello"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object cannot be interpreted as an integer

>>> arr[1] = 300
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: byte must be in range(0, 256)

>>> # Bytearrays can be converted back into bytes objects:
>>> # (This will copy the data)
>>> bytes(arr)
b'\x00\x02\x03*'


Массивы в Python: Краткое описание
Существует несколько встроенных структур данных, из которых вы можете выбирать, когда речь заходит о реализации массивов в Python. В этом разделе вы сосредоточились на основных функциях языка и структурах данных, включенных в стандартную библиотеку.
Если вы хотите выйти за рамки стандартной библиотеки Python, то сторонние пакеты, такие как NumPy и pandas, предлагают широкий спектр о быстрых реализациях массивов для научных вычислений и обработки данных.
Если вы хотите ограничиться структурами данных array, входящими в состав Python, то вот несколько рекомендаций:


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


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


Если у вас есть текстовые данные, представленные в виде символов Unicode, то используйте встроенный в Python str. Если вам нужна изменяемая структура данных в виде строки, то используйте list символов.


Если вы хотите сохранить непрерывный блок байтов, то используйте неизменяемый тип bytes или bytearray, если вам нужна изменяемая структура данных.


В большинстве случаев я предпочитаю начинать с простого list. Позже я буду специализироваться только в том случае, если возникнет проблема с производительностью или объемом памяти. В большинстве случаев использование структуры данных с массивами общего назначения, такой как list, обеспечивает максимальную скорость разработки и удобство программирования.
Я обнаружил, что вначале это обычно гораздо важнее, чем пытаться выжать все до последней капли из производительности с самого начала.
Записи, структуры и объекты передачи данных
По сравнению с массивами, структуры данных record содержат фиксированное количество полей. Каждое поле может иметь имя, а также может иметь другой тип.
В этом разделе вы увидите, как реализовать записи, структуры и обычные объекты данных в Python, используя только встроенные типы данных и классы из стандартной библиотеки.
 Примечание: Здесь я использую определение записи в широком смысле. Например, я также собираюсь обсудить такие типы, как встроенный в Python tuple, которые могут считаться, а могут и не считаться записями в строгом смысле этого слова, поскольку они не содержат именованных полей.
Python предлагает несколько типов данных, которые вы можете использовать для реализации записей, структур и объектов передачи данных. В этом разделе вы получите краткий обзор каждой реализации и ее уникальных характеристик. В конце вы найдете краткое изложение и руководство по принятию решений, которые помогут вам сделать свой собственный выбор.
 Примечание: Это руководство адаптировано из главы “Общие структуры данных в Python” в книге  Приемы работы с Python: Книга. Если вам нравится то, что вы читаете, то обязательно ознакомьтесь с  остальной частью книги.
Хорошо, давайте начнем!
dict: Простые объекты данных
Как упоминалось ранее, словари Python хранят произвольное количество объектов, каждый из которых идентифицируется уникальным ключом. Словари также часто называются картами или ассоциативными массивами и позволяют эффективно выполнять поиск, вставку и удаление любого объекта, связанного с данным ключом.
Возможно использование словарей в качестве типа данных записи или объекта данных в Python. Словари легко создавать на Python, поскольку они имеют свой собственный синтаксический сахар, встроенный в язык в виде словарных литералов. Синтаксис словаря лаконичен и довольно удобен для ввода.
Объекты данных, созданные с помощью словарей, могут изменяться, и существует слабая защита от неправильного написания имен полей, поскольку поля можно свободно добавлять и удалять в любое время. Оба этих свойства могут привести к неожиданным ошибкам, и всегда нужно выбирать между удобством и устойчивостью к ошибкам:

>>> car1 = {
...     "color": "red",
...     "mileage": 3812.4,
...     "automatic": True,
... }
>>> car2 = {
...     "color": "blue",
...     "mileage": 40231,
...     "automatic": False,
... }

>>> # Dicts have a nice repr:
>>> car2
{'color': 'blue', 'automatic': False, 'mileage': 40231}

>>> # Get mileage:
>>> car2["mileage"]
40231

>>> # Dicts are mutable:
>>> car2["mileage"] = 12
>>> car2["windshield"] = "broken"
>>> car2
{'windshield': 'broken', 'color': 'blue',
 'automatic': False, 'mileage': 12}

>>> # No protection against wrong field names,
>>> # or missing/extra fields:
>>> car3 = {
...     "colr": "green",
...     "automatic": False,
...     "windshield": "broken",
... }


tuple: Неизменяемые группы объектов
Кортежи в Python представляют собой простую структуру данных для группировки произвольных объектов. Кортежи неизменяемы — их нельзя изменить после их создания.
С точки зрения производительности, кортежи занимают немного меньше памяти, чем списки в CPython, и их также быстрее создавать.
Как вы можете видеть из приведенного ниже разбора байт-кода, для создания константы кортежа требуется один LOAD_CONST код операции, в то время как для создания объекта list с таким же содержимым требуется еще несколько операций:

>>> import dis
>>> dis.dis(compile("(23, 'a', 'b', 'c')", "", "eval"))
      0 LOAD_CONST           4 ((23, "a", "b", "c"))
      3 RETURN_VALUE

>>> dis.dis(compile("[23, 'a', 'b', 'c']", "", "eval"))
      0 LOAD_CONST           0 (23)
      3 LOAD_CONST           1 ('a')
      6 LOAD_CONST           2 ('b')
      9 LOAD_CONST           3 ('c')
     12 BUILD_LIST           4
     15 RETURN_VALUE


Однако вам не следует придавать слишком большого значения этим различиям. На практике разница в производительности часто бывает незначительной, и попытка выжать из программы дополнительную производительность, переключившись со списков на кортежи, скорее всего, будет неправильным подходом.
Потенциальным недостатком простых кортежей является то, что данные, которые вы храните в них, можно извлечь, только обратившись к ним через целочисленные индексы. Вы не можете присвоить имена отдельным свойствам, хранящимся в кортеже. Это может повлиять на читаемость кода.
Кроме того, кортеж - это всегда специальная структура: трудно гарантировать, что два кортежа будут содержать одинаковое количество полей и одинаковые свойства, хранящиеся в них.
Это упрощает внесение ошибок по ошибке, таких как путаница в порядке следования полей. Поэтому я бы рекомендовал, чтобы количество полей, хранящихся в кортеже, было как можно меньшим:

>>> # Fields: color, mileage, automatic
>>> car1 = ("red", 3812.4, True)
>>> car2 = ("blue", 40231.0, False)

>>> # Tuple instances have a nice repr:
>>> car1
('red', 3812.4, True)
>>> car2
('blue', 40231.0, False)

>>> # Get mileage:
>>> car2[1]
40231.0

>>> # Tuples are immutable:
>>> car2[1] = 12
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

>>> # No protection against missing or extra fields
>>> # or a wrong order:
>>> car3 = (3431.5, "green", True, "silver")


Написать пользовательский класс: Больше работы, больше контроля
 Классы позволяют вам определять повторно используемые схемы элементов для объектов данных, чтобы гарантировать, что каждый объект предоставляет одинаковый набор полей.
Использование обычных  классов Python в качестве типов данных для записи возможно, но также требуется ручная работа, чтобы получить удобные функции других реализаций. Например, добавление новых полей в конструктор __init__ является многословным и требует времени.
Кроме того, строковое представление по умолчанию для объектов, созданных из пользовательских классов, не очень полезно. Чтобы исправить это, вам, возможно, придется добавить свой собственный __repr__ метод, который, опять же, обычно довольно подробен и должен обновляться каждый раз, когда вы добавляете новое поле.
Поля, хранящиеся в классах, изменяемы, и новые поля могут быть добавлены свободно, что вам может понравиться, а что нет. Можно обеспечить больший контроль доступа и создать поля, доступные только для чтения, используя @property декоратор, но, опять же, для этого требуется написать больше кода для склеивания.
Создание пользовательского класса - отличный вариант, когда вы хотите добавить бизнес-логику и поведение к своим объектам записей с помощью методов. Однако это означает, что технически эти объекты больше не являются обычными объектами данных:

>>> class Car:
...     def __init__(self, color, mileage, automatic):
...         self.color = color
...         self.mileage = mileage
...         self.automatic = automatic
...
>>> car1 = Car("red", 3812.4, True)
>>> car2 = Car("blue", 40231.0, False)

>>> # Get the mileage:
>>> car2.mileage
40231.0

>>> # Classes are mutable:
>>> car2.mileage = 12
>>> car2.windshield = "broken"

>>> # String representation is not very useful
>>> # (must add a manually written __repr__ method):
>>> car1
<Car object at 0x1081e69e8>


dataclasses.dataclass: Python 3.7+ Классы данных
 Классы данных доступны в Python версии 3.7 и выше. Они представляют собой отличную альтернативу определению ваших собственных классов хранения данных с нуля.
При написании класса данных вместо обычного класса Python экземпляры ваших объектов получают несколько полезных функций "из коробки", которые сэкономят вам время на ввод текста и ручную реализацию:

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

Классы данных обычно создаются с помощью @dataclass декоратора, как вы увидите в примере кода ниже:

>>> from dataclasses import dataclass
>>> @dataclass
... class Car:
...     color: str
...     mileage: float
...     automatic: bool
...
>>> car1 = Car("red", 3812.4, True)

>>> # Instances have a nice repr:
>>> car1
Car(color='red', mileage=3812.4, automatic=True)

>>> # Accessing fields:
>>> car1.mileage
3812.4

>>> # Fields are mutable:
>>> car1.mileage = 12
>>> car1.windshield = "broken"

>>> # Type annotations are not enforced without
>>> # a separate type checking tool like mypy:
>>> Car("red", "NOT_A_FLOAT", 99)
Car(color='red', mileage='NOT_A_FLOAT', automatic=99)


Чтобы узнать больше о классах данных Python, ознакомьтесь с Основным руководством по классам данных в Python 3.7.
collections.namedtuple: Удобные объекты данных
Класс namedtuple, доступный в Python 2.6+, предоставляет расширение встроенного типа данных tuple. Аналогично определению пользовательского класса, использование namedtuple позволяет вам определять повторно используемые схемы элементов для ваших записей, которые гарантируют использование правильных имен полей.
namedtuple объекты неизменяемы, как и обычные кортежи. Это означает, что вы не сможете добавлять новые поля или изменять существующие после создания экземпляра namedtuple.
Кроме того, namedtuple объекты - это, ну. . . именованные кортежи. Доступ к каждому объекту, хранящемуся в них, возможен с помощью уникального идентификатора. Это избавляет вас от необходимости запоминать целочисленные индексы или прибегать к обходным путям, таким как определение целочисленных констант в качестве мнемоники для ваших индексов.
namedtuple объекты реализованы как обычные классы Python внутри системы. Что касается использования памяти, они также лучше, чем обычные классы, и так же эффективны с точки зрения памяти, как и обычные кортежи:

>>> from collections import namedtuple
>>> from sys import getsizeof

>>> p1 = namedtuple("Point", "x y z")(1, 2, 3)
>>> p2 = (1, 2, 3)

>>> getsizeof(p1)
64
>>> getsizeof(p2)
64


namedtuple объекты могут быть простым способом очистить ваш код и сделать его более читаемым за счет улучшения структуры ваших данных.
Я нахожу, что переход от специальных типов данных, таких как словари с фиксированным форматом, к объектам namedtuple помогает мне более четко выразить цель моего кода. Часто, когда я применяю этот рефакторинг, я волшебным образом нахожу лучшее решение проблемы, с которой сталкиваюсь.
 Примечание: Чтобы глубже разобраться в namedtuple, ознакомьтесь   с руководством по написанию кода на Python и его очистке с помощью namedtuple.
Чтобы избежать путаницы, вот краткое описание того, как используется каждый термин в руководстве:
 Использование объектов namedtuple поверх обычных (неструктурированных) кортежей и диктовок также может облегчить жизнь ваших коллег, сделав передаваемые данные самодокументируемыми, по крайней мере, до некоторой степени:

>>> from collections import namedtuple
>>> Car = namedtuple("Car" , "color mileage automatic")
>>> car1 = Car("red", 3812.4, True)

>>> # Instances have a nice repr:
>>> car1
Car(color="red", mileage=3812.4, automatic=True)

>>> # Accessing fields:
>>> car1.mileage
3812.4

>>> # Fields are immtuable:
>>> car1.mileage = 12
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: can't set attribute

>>> car1.windshield = "broken"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'Car' object has no attribute 'windshield'


typing.NamedTuple: Улучшенные именованные наборы
Добавлено в Python 3.6, typing.NamedTuple является младшим братом класса namedtuple в модуле collections. Это очень похоже на namedtuple, с основным отличием, заключающимся в обновленном синтаксисе для определения новых типов записей и добавленной поддержке подсказок по типу .
Пожалуйста, обратите внимание, что аннотации к типам не применяются без отдельного инструмента проверки типов, такого как mypy. Но даже без поддержки инструментов они могут содержать полезные подсказки для других программистов (или быть ужасно запутанными, если подсказки по типу устарели):

>>> from typing import NamedTuple

>>> class Car(NamedTuple):
...     color: str
...     mileage: float
...     automatic: bool

>>> car1 = Car("red", 3812.4, True)

>>> # Instances have a nice repr:
>>> car1
Car(color='red', mileage=3812.4, automatic=True)

>>> # Accessing fields:
>>> car1.mileage
3812.4

>>> # Fields are immutable:
>>> car1.mileage = 12
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: can't set attribute

>>> car1.windshield = "broken"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'Car' object has no attribute 'windshield'

>>> # Type annotations are not enforced without
>>> # a separate type checking tool like mypy:
>>> Car("red", "NOT_A_FLOAT", 99)
Car(color='red', mileage='NOT_A_FLOAT', automatic=99)


struct.Struct: Сериализованные структуры на языке Си
Класс struct.Struct преобразует значения Python и структуры C, сериализованные в объекты Python bytes. Например, его можно использовать для обработки двоичных данных, хранящихся в файлах или поступающих из сетевых подключений.
Структуры определяются с помощью мини-языка, основанного на строках формата, который позволяет вам определять расположение различных типов данных C, таких как char, int, и long, а также их unsigned вариантов.
Сериализованные структуры редко используются для представления объектов данных, которые должны обрабатываться исключительно внутри кода Python. Они предназначены в первую очередь как формат обмена данными, а не как способ хранения данных в памяти, который используется только в коде на Python.
В некоторых случаях для упаковки примитивных данных в структуры может потребоваться меньше памяти, чем для хранения данных других типов. Однако в большинстве случаев это было бы довольно сложной (и, вероятно, ненужной) оптимизацией:

>>> from struct import Struct
>>> MyStruct = Struct("i?f")
>>> data = MyStruct.pack(23, False, 42.0)

>>> # All you get is a blob of data:
>>> data
b'\x17\x00\x00\x00\x00\x00\x00\x00\x00\x00(B'

>>> # Data blobs can be unpacked again:
>>> MyStruct.unpack(data)
(23, False, 42.0)


types.SimpleNamespace: Необычный доступ к атрибутам
Вот еще один немного неясный вариант реализации объектов данных в Python: types.SimpleNamespace. Этот класс был добавлен в Python 3.3 и предоставляет доступ к атрибутам своего пространства имен.
Это означает, что экземпляры SimpleNamespace предоставляют все свои ключи в качестве атрибутов класса. Вы можете использовать obj.key пунктирный доступ к атрибуту вместо синтаксиса индексации в квадратных скобках obj['key'], который используется в обычных dicts. По умолчанию все экземпляры также содержат значимый символ __repr__.
Как следует из названия, SimpleNamespace - это просто! По сути, это словарь, который предоставляет доступ к атрибутам и хорошо печатается. Атрибуты можно свободно добавлять, изменять и удалять:

>>> from types import SimpleNamespace
>>> car1 = SimpleNamespace(color="red", mileage=3812.4, automatic=True)

>>> # The default repr:
>>> car1
namespace(automatic=True, color='red', mileage=3812.4)

>>> # Instances support attribute access and are mutable:
>>> car1.mileage = 12
>>> car1.windshield = "broken"
>>> del car1.automatic
>>> car1
namespace(color='red', mileage=12, windshield='broken')


Записи, структуры и объекты данных в Python: Краткое описание
Как вы уже видели, существует довольно много различных вариантов реализации записей или объектов данных. Какой тип данных следует использовать для объектов данных в Python?  Как правило, ваше решение будет зависеть от вашего варианта использования:


Если у вас всего несколько полей, то использование простого объекта tuple может быть приемлемым, если порядок расположения полей легко запомнить или названия полей излишни. Например, представьте себе (x, y, z) точку в трехмерном пространстве.


Если вам нужны неизменяемые поля, то хорошими вариантами являются простые кортежи, collections.namedtuple и typing.NamedTuple.


Если вам нужно заблокировать названия полей, чтобы избежать опечаток, то collections.namedtuple и typing.NamedTuple - ваши друзья.


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


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


Если вам нужно добавить поведение (методы) к объекту, то вам следует написать пользовательский класс либо с нуля, либо с помощью dataclass декоратора, либо путем расширения collections.namedtuple или typing.NamedTuple.


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


Если вы ищете безопасный вариант по умолчанию, то моей общей рекомендацией для реализации простой записи, структуры или объекта данных в Python было бы использовать collections.namedtuple в Python 2.x и его младшем собрате, typing.NamedTuple в Python 3.
Наборы и мультимножества
В этом разделе вы увидите, как реализовать изменяемые и неизменяемые структуры данных set и multiset (пакет) в Python, используя встроенные типы данных и классы из стандартной библиотеки. 
Набор  - это неупорядоченная коллекция объектов, которая не допускает дублирования элементов. Как правило, наборы используются для быстрой проверки значения на принадлежность к набору, для вставки или удаления новых значений из набора и для вычисления объединения или пересечения двух наборов.
При правильной реализации set ожидается, что тесты на принадлежность будут выполняться быстро O(1). Операции объединения, пересечения, разности и подмножества должны занимать в среднем O(n) времени. Реализации set, включенные в стандартную библиотеку Python , соответствуют этим характеристикам производительности.
Как и словари, наборы обрабатываются в Python особым образом и содержат некоторый синтаксический сахар, который упрощает их создание. Например, синтаксис выражения set с фигурными скобками и значения set позволяют удобно определять новые экземпляры set:

vowels = {"a", "e", "i", "o", "u"}
squares = {x * x for x in range(10)}


Но будьте осторожны: чтобы создать пустой набор, вам нужно вызвать конструктор set(). Использование пустых фигурных скобок ({}) неоднозначно и приведет к созданию пустого словаря.
Python и его стандартная библиотека предоставляют несколько реализаций set. Давайте рассмотрим их.
set: Ваш основной набор
 set Тип - это встроенная реализация set в Python. Он изменяем и позволяет динамически вставлять и удалять элементы.
Наборы данных 
 В Python поддерживаются типом данных dict и имеют те же характеристики производительности. Любой хэшируемый объект может быть сохранен в виде набора:

>>> vowels = {"a", "e", "i", "o", "u"}
>>> "e" in vowels
True

>>> letters = set("alice")
>>> letters.intersection(vowels)
{'a', 'e', 'i'}

>>> vowels.add("x")
>>> vowels
{'i', 'a', 'u', 'o', 'x', 'e'}

>>> len(vowels)
6


frozenset: Неизменяемые множества
Класс frozenset реализует неизменяемую версию set, которая не может быть изменена после ее создания. 
frozenset объекты статичны и допускают только операции запроса к своим элементам, а не вставки или удаления. Поскольку объекты frozenset являются статическими и хэшируемыми, их можно использовать как ключи словаря или как элементы другого набора, что невозможно с обычными (изменяемыми) объектами set:

>>> vowels = frozenset({"a", "e", "i", "o", "u"})
>>> vowels.add("p")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'frozenset' object has no attribute 'add'

>>> # Frozensets are hashable and can
>>> # be used as dictionary keys:
>>> d = { frozenset({1, 2, 3}): "hello" }
>>> d[frozenset({1, 2, 3})]
'hello'


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

>>> from collections import Counter
>>> inventory = Counter()

>>> loot = {"sword": 1, "bread": 3}
>>> inventory.update(loot)
>>> inventory
Counter({'bread': 3, 'sword': 1})

>>> more_loot = {"sword": 1, "apple": 1}
>>> inventory.update(more_loot)
>>> inventory
Counter({'bread': 3, 'sword': 2, 'apple': 1})


Одно предостережение для класса Counter заключается в том, что вам следует быть осторожным при подсчете количества элементов в объекте Counter. Вызов len() возвращает количество уникальных элементов в мультисети, тогда как общее количество  элементов может быть получено с помощью sum():

>>> len(inventory)
3  # Unique elements

>>> sum(inventory.values())
6  # Total no. of elements


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

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

Стеки (LIFOs)
Стек - это набор объектов, который поддерживает семантику быстрого Ввода/вывода последним (LIFO) для вставки и удаления. В отличие от списков или массивов, стеки обычно не допускают произвольного доступа к содержащимся в них объектам. Операции вставки и удаления также часто называются push и pop.
Полезной аналогией структуры данных stack из реального мира является стопка листов. Новые листы добавляются в верхнюю часть стопки, а поскольку листы дорогие и тяжелые, перемещать можно только самую верхнюю пластину. Другими словами, последняя тарелка в стопке должна быть снята первой (LIFO). Чтобы добраться до тарелок, которые находятся ниже в стопке, самые верхние тарелки должны быть сняты одна за другой.
С точки зрения производительности, надлежащая реализация стека, как ожидается, займет O(1) время для операций вставки и удаления.
Стеки широко используются в алгоритмах. Например, они используются для синтаксического анализа языка, а также для управления памятью во время выполнения, что основано на стеке вызовов. Коротким и красивым алгоритмом, использующим стек, является поиск в глубину (DFS) в древовидной или графической структуре данных.
Python поставляется с несколькими реализациями стека, каждая из которых имеет несколько разные характеристики. Давайте взглянем на них и сравним их характеристики.
list: Простые встроенные стеки
 Встроенный в Python list тип создает достойную структуру стековых данных, поскольку он поддерживает операции push и pop в амортизированном  O(1) время.
 Списки в Python реализованы как динамические массивы, что означает, что им иногда требуется изменять размер пространства для хранения элементов, хранящихся в них, при добавлении или удалении элементов. Список перераспределяет резервное хранилище, так что не каждый push-запрос требует изменения размера. В результате вы получаете амортизированную O(1) временную сложность для этих операций.
Недостатком является то, что это делает их производительность менее стабильной, чем стабильная O(1) вставки и удаления, предоставляемые реализацией на основе связанных списков (как вы увидите ниже на примере collections.deque). С другой стороны, списки обеспечивают быстрый O(1) произвольный доступ к элементам в стеке во времени, и это может быть дополнительным преимуществом.
При использовании списков в качестве стеков необходимо учитывать важный нюанс производительности: чтобы получить амортизированную O(1) производительность при вставке и удалении, в список должны быть добавлены новые элементы. завершите список с помощью метода append() и снова удалите из конца с помощью метода pop(). Для достижения оптимальной производительности стеки, основанные на списках Python, должны увеличиваться в сторону более высоких индексов и уменьшаться в сторону более низких.
Добавление и удаление с лицевой стороны выполняется намного медленнее и занимает O(n времени, поскольку существующие элементы необходимо перемещать по кругу чтобы освободить место для нового элемента. Это представление антипаттерн, которого вам следует избегать, насколько это возможно:

>>> s = []
>>> s.append("eat")
>>> s.append("sleep")
>>> s.append("code")

>>> s
['eat', 'sleep', 'code']

>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'

>>> s.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from empty list


collections.deque: Быстрые и надежные штабелеры
Класс deque реализует двухстороннюю очередь, которая поддерживает добавление и удаление элементов с обоих концов за время O(1) (без учета амортизации). Поскольку deques одинаково хорошо поддерживают добавление и удаление элементов с обоих концов, они могут использоваться как в качестве очередей, так и в качестве стеков.
 Объекты deque в Python реализованы в виде двусвязных списков, что обеспечивает им отличную и согласованную производительность при вставке и удалении элементов, но низкую O( n) производительность при случайном доступе к элементам в середине стека.
В целом, collections.deque это отличный выбор, если вы ищете стековую структуру данных в стандартной библиотеке Python, которая обладает характеристиками производительности реализации со связанными списками:

>>> from collections import deque
>>> s = deque()
>>> s.append("eat")
>>> s.append("sleep")
>>> s.append("code")

>>> s
deque(['eat', 'sleep', 'code'])

>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'

>>> s.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from an empty deque


queue.LifoQueue: Семантика блокировки для параллельных вычислений
 LifoQueue Реализация стека в стандартной библиотеке Python синхронизирована и обеспечивает семантику блокировки для поддержки нескольких параллельных производителей и потребителей.
Помимо LifoQueue, модуль queue содержит несколько других классов, реализующих очереди с несколькими производителями и несколькими потребителями, которые полезны для параллельных вычислений.
В зависимости от вашего варианта использования семантика блокировки может оказаться полезной, а может просто привести к ненужным накладным расходам. В этом случае вам было бы лучше использовать list или deque в качестве стека общего назначения:

>>> from queue import LifoQueue
>>> s = LifoQueue()
>>> s.put("eat")
>>> s.put("sleep")
>>> s.put("code")

>>> s
<queue.LifoQueue object at 0x108298dd8>

>>> s.get()
'code'
>>> s.get()
'sleep'
>>> s.get()
'eat'

>>> s.get_nowait()
queue.Empty

>>> s.get()  # Blocks/waits forever...


Реализации стека в Python: Краткое описание
Как вы уже видели, Python поставляется с несколькими реализациями стековой структуры данных. Все они имеют несколько разные характеристики, а также компромиссы в производительности и использовании.
Если вам не нужна поддержка  параллельной обработки (или если вы не хотите обрабатывать блокировку и разблокировку вручную), то ваш выбор сводится к встроенной list введите или collections.deque. Разница заключается в структуре данных, используемой за кулисами, и общей простоте использования.
list поддерживается динамическим массивом, что делает его отличным для быстрого произвольного доступа, но требует периодического изменения размера при добавлении или удалении элементов. 
В списке избыточно выделяется резервное хранилище, так что не при каждом нажатии или возврате требуется изменять размер, и вы получаете амортизированную O(1) временную сложность для этих операций. Но вам нужно быть осторожным и вставлять и удалять элементы только с помощью append() и pop(). В противном случае производительность снижается до O(n).
collections.deque поддерживается двусвязным списком, который оптимизирует добавление и удаление с обоих концов и обеспечивает согласованную производительность O(1) для этих операций. Класс deque не только более стабилен в работе, но и проще в использовании, поскольку вам не нужно беспокоиться о добавлении или удалении элементов не с того конца.
Таким образом, collections.deque является отличным выбором для реализации стека (очереди LIFO) в Python.
Очереди (FIFOs)
В этом разделе вы увидите, как реализовать структуру данных очереди Первый вход/первый выход (FIFO), используя только встроенные типы данных и классы из стандартной библиотеки Python. 
Очередь  - это набор объектов, который поддерживает быструю семантику FIFO для вставки и удаления. Операции вставки и удаления иногда называются постановкой в очередь и выводом из очереди. В отличие от списков или массивов, очереди обычно не допускают произвольного доступа к содержащимся в них объектам.
Вот реальная аналогия для очереди FIFO: 
Представьте себе очередь из специалистов по питону, ожидающих получения своих бейджей конференции в первый день регистрации на PyCon. Когда новые участники заходят на место проведения конференции и встают в очередь для получения своих бейджей, они встают в очередь (enqueue) в конце очереди. Разработчики получают свои бейджи и сумки с сувенирами для конференции, а затем выходят из очереди (dequeue) в начале очереди.
Еще один способ запомнить характеристики структуры данных очереди - представить ее в виде канала. Вы добавляете шарики для пинг-понга в один конец, они перемещаются в другой конец, где вы их удаляете. Пока шары находятся в очереди (сплошной металлической трубе), вы не сможете до них добраться. Единственный способ взаимодействовать с шарами в очереди - добавлять новые в конце трубы (ставить в очередь) или удалять их в начале (выводить из очереди).
Очереди похожи на стеки. Разница между ними заключается в способе удаления элементов. С помощью очереди вы удаляете элемент , который был добавлен меньше всего (FIFO), но со стеком , вы удаляете элемент , который был добавлен больше всего за последнее время (LIFO).
 С точки зрения производительности, ожидается, что правильная реализация очереди займет O(1) время для операций вставки и удаления. Это две основные операции, выполняемые в очереди, и при правильной реализации они должны быть быстрыми.
Очереди имеют широкий спектр применений в алгоритмах и часто помогают решать задачи планирования и параллельного программирования. Коротким и красивым алгоритмом, использующим очередь, является поиск по ширине (BFS) в древовидной или графической структуре данных.
Алгоритмы планирования часто используют приоритетные очереди внутри системы. Это специализированные очереди. Вместо извлечения следующего элемента по времени вставки, очередь с приоритетом извлекает  элемент с наивысшим приоритетом. Приоритет отдельных элементов определяется очередью на основе порядка, применяемого к их ключам. 
Однако в обычной очереди порядок элементов, которые в ней хранятся, не меняется. Как и в примере с конвейером, вы получаете то, что положили, и именно в таком порядке.
Python поставляется с несколькими реализациями очереди, каждая из которых имеет несколько разные характеристики. Давайте рассмотрим их.
list: Ужасно длинные очереди
Можно  использовать обычный list в качестве очереди, но это не идеально с точки зрения производительности. Списки для этой цели работают довольно медленно, поскольку для вставки или удаления элемента в начале требуется сдвинуть все остальные элементы на единицу, что требует O(n) времени.
Поэтому я бы не  рекомендовал использовать list в качестве временной очереди в Python, если только вы не имеете дело с небольшим количеством элементов:

>>> q = []
>>> q.append("eat")
>>> q.append("sleep")
>>> q.append("code")

>>> q
['eat', 'sleep', 'code']

>>> # Careful: This is slow!
>>> q.pop(0)
'eat'


collections.deque: Быстрые и надежные очереди
Класс deque реализует двустороннюю очередь, которая поддерживает добавление и удаление элементов с обоих концов за O(1) время (без учета амортизации). Поскольку deques одинаково хорошо поддерживают добавление и удаление элементов с обоих концов, они могут использоваться как в качестве очередей, так и в качестве стеков.
 Объекты deque в Python реализованы в виде двусвязных списков. Это обеспечивает им отличную и стабильную производительность при вставке и удалении элементов, но низкую производительность O(n) при случайном доступе к элементам в середине стека.
В результате, collections.deque является отличным выбором по умолчанию, если вы ищете структуру данных очереди в стандартной библиотеке Python:

>>> from collections import deque
>>> q = deque()
>>> q.append("eat")
>>> q.append("sleep")
>>> q.append("code")

>>> q
deque(['eat', 'sleep', 'code'])

>>> q.popleft()
'eat'
>>> q.popleft()
'sleep'
>>> q.popleft()
'code'

>>> q.popleft()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from an empty deque


queue.Queue: Семантика блокировки для параллельных вычислений
Реализация queue.Queue в стандартной библиотеке Python синхронизирована и предоставляет семантику блокировки для поддержки нескольких одновременных производителей и потребителей.
Модуль queue содержит несколько других классов, реализующих очереди с несколькими производителями и несколькими потребителями, которые полезны для параллельных вычислений.
В зависимости от вашего варианта использования семантика блокировки может оказаться полезной или просто привести к ненужным накладным расходам. В этом случае вам лучше использовать collections.deque в качестве очереди общего назначения:

>>> from queue import Queue
>>> q = Queue()
>>> q.put("eat")
>>> q.put("sleep")
>>> q.put("code")

>>> q
<queue.Queue object at 0x1070f5b38>

>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'

>>> q.get_nowait()
queue.Empty

>>> q.get()  # Blocks/waits forever...


multiprocessing.Queue: Общие очереди заданий
multiprocessing.Queue это реализация   общей   очереди заданий, которая позволяет нескольким одновременно работающим сотрудникам параллельно обрабатывать элементы, находящиеся в очереди. Распараллеливание на основе процессов популярно в CPython из-за глобальной блокировки интерпретатора (GIL), которая предотвращает некоторые формы параллельного выполнения в одном процессе интерпретатора.
Как специализированная реализация очереди, предназначенная для обмена данными между процессами, multiprocessing.Queue упрощает распределение работы между несколькими процессами, чтобы обойти ограничения GIL. Этот тип очереди может хранить и передавать любой  объект, который можно выбрать, через границы процесса:

>>> from multiprocessing import Queue
>>> q = Queue()
>>> q.put("eat")
>>> q.put("sleep")
>>> q.put("code")

>>> q
<multiprocessing.queues.Queue object at 0x1081c12b0>

>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'

>>> q.get()  # Blocks/waits forever...


Очереди в Python: краткое описание
Python включает в себя несколько реализаций очереди как часть основного языка и его стандартной библиотеки. 
list объекты можно использовать в качестве очередей, но обычно это не рекомендуется из-за низкой производительности.
Если вам не нужна поддержка параллельной обработки, то реализация, предлагаемая collections.deque, является отличным выбором по умолчанию для реализации структуры данных очереди FIFO в Python. Он обеспечивает характеристики производительности, которые можно было бы ожидать от хорошей реализации очереди, а также может использоваться в качестве стека (LIFO queue).
Приоритетные очереди
Очередь с приоритетом  представляет собой контейнерную структуру данных, которая управляет набором записей с помощью полностью упорядоченных ключей для обеспечения быстрого доступа к запишите с помощью самого маленького или самого большого ключа в наборе.
Очередь с приоритетом можно рассматривать как измененную очередь. Вместо того, чтобы извлекать следующий элемент по времени вставки, он извлекает элемент с наивысшим приоритетом. Приоритет отдельных элементов определяется порядком, применяемым к их ключам.
Очереди с приоритетами обычно используются для решения проблем планирования. Например, вы можете использовать их, чтобы отдавать приоритет задачам повышенной срочности.
Подумайте о работе планировщика задач операционной системы:
В идеале системные задачи с более высоким приоритетом (например, игра в режиме реального времени) должны иметь приоритет над задачами с более низким приоритетом (например, загрузка обновлений в фоновом режиме). Организуя отложенные задачи в приоритетную очередь, в которой в качестве ключевого параметра используется срочность задачи, планировщик задач может быстро выбрать задачи с наивысшим приоритетом и разрешить их выполнение в первую очередь.
В этом разделе вы увидите несколько вариантов того, как вы можете реализовать приоритетные очереди в Python, используя встроенные структуры данных или структуры данных, включенные в стандартную библиотеку Python. У каждой реализации будут свои плюсы и минусы, но, на мой взгляд, для большинства распространенных сценариев есть очевидный победитель. Давайте выясним, какой из них лучше.
list: Очереди, отсортированные вручную
Вы можете использовать отсортированный list, чтобы быстро определить и удалить самый маленький или самый большой элемент. Недостатком является то, что вставка новых элементов в список является медленной операцией (O(n).
В то время как точку вставки можно найти за O(log n) времени, используя bisect.insort в стандартной библиотеке при этом всегда преобладает медленный этап вставки.
Поддержание порядка путем добавления в список и повторной сортировки также занимает не менее O(n log n времени. Другим недостатком является то, что вам приходится вручную выполнять повторную сортировку списка при добавлении новых элементов. Пропуск этого шага может привести к возникновению ошибок, и ответственность за это всегда ложится на вас, разработчика.
Это означает, что отсортированные списки подходят в качестве приоритетных очередей только в том случае, если вставок будет немного:

>>> q = []
>>> q.append((2, "code"))
>>> q.append((1, "eat"))
>>> q.append((3, "sleep"))
>>> # Remember to re-sort every time a new element is inserted,
>>> # or use bisect.insort()
>>> q.sort(reverse=True)

>>> while q:
...     next_item = q.pop()
...     print(next_item)
...
(1, 'eat')
(2, 'code')
(3, 'sleep')


heapq: Двоичные кучи на основе списков
heapq это реализация двоичной кучи, обычно поддерживаемая простым list, и она поддерживает вставку и извлечение наименьшего элемента в O(журнал n) времени.
Этот модуль является хорошим выбором для реализации приоритетных очередей в Python. Поскольку heapq технически обеспечивает только минимальную загрузку, необходимо предпринять дополнительные шаги для обеспечения стабильности сортировки и других функций, обычно ожидаемых от практической приоритетной очереди:

>>> import heapq
>>> q = []
>>> heapq.heappush(q, (2, "code"))
>>> heapq.heappush(q, (1, "eat"))
>>> heapq.heappush(q, (3, "sleep"))

>>> while q:
...     next_item = heapq.heappop(q)
...     print(next_item)
...
(1, 'eat')
(2, 'code')
(3, 'sleep')


queue.PriorityQueue: Красивые очереди с приоритетами
queue.PriorityQueue использует heapq внутренне и разделяет те же временные и пространственные сложности. Разница в том, что PriorityQueue синхронизирован и обеспечивает семантику блокировки для поддержки нескольких одновременных производителей и потребителей.
В зависимости от вашего варианта использования это может быть полезно или просто немного замедлить работу вашей программы. В любом случае, вы можете предпочесть интерфейс на основе классов, предоставляемый PriorityQueue, интерфейсу на основе функций, предоставляемому heapq:

>>> from queue import PriorityQueue
>>> q = PriorityQueue()
>>> q.put((2, "code"))
>>> q.put((1, "eat"))
>>> q.put((3, "sleep"))

>>> while not q.empty():
...     next_item = q.get()
...     print(next_item)
...
(1, 'eat')
(2, 'code')
(3, 'sleep')


Приоритетные очереди в Python: Краткое описание
Python включает в себя несколько реализаций приоритетной очереди, готовых к использованию.
queue.PriorityQueue выделяется из общего ряда приятным объектно-ориентированным интерфейсом и названием, которое четко указывает на его назначение. Это должно быть вашим предпочтительным выбором.
Если вы хотите избежать накладных расходов на блокировку, связанных с queue.PriorityQueue, то использование модуля heapq напрямую также является хорошим вариантом.
Заключение: Структуры данных Python
На этом ваш экскурс в общие структуры данных в Python завершен. Благодаря полученным здесь знаниям вы готовы реализовать эффективные структуры данных, которые подходят именно для вашего конкретного алгоритма или варианта использования.
 В этом уроке вы узнали:

Какие распространенные абстрактные типы данных встроены в стандартную библиотеку Python
Как наиболее распространенные абстрактные типы данных соотносятся со схемой именования в Python 
Как использовать абстрактные типы данных для практического использования в различных алгоритмах

Если вам понравилось то, что вы узнали из этого примера из Трюков с Python, то обязательно ознакомьтесь с остальной частью книги. 
Если вы заинтересованы в том, чтобы освежить свои общие знания о структурах данных, то я настоятельно рекомендую Руководство по разработке алгоритмов Стивена С. Скиены . Это обеспечивает отличный баланс между обучением фундаментальным (и более продвинутым) структурам данных и демонстрацией того, как реализовать их в вашем коде. Книга Стива оказала большую помощь при написании этого руководства.
<статус завершения article-slug="python-data-structures" class="btn-group mb-0" data-api-article-bookmark-url="/api/v1/articles/python-data-structures/bookmark/" data-api-article-завершение-status-url="/api/v1/articles/python-структуры данных/завершение_статуса/">



<кнопка поделиться bluesky-text="Интересная статья на #Python от @realpython.com :" email-body="Ознакомьтесь с этой статьей о Python:%0A%0общие структуры данных Python (руководство)" email-subject="Статья о Python для вас" twitter-text="Интересная статья о Python от @realpython:" url="https://realpython.com/python-data-structures /" url-title="Общие структуры данных Python (руководство)">

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

                







                 Back to Top