5. Общие структуры данных Python

Что должен применять на практике и что должен твердо знать каждый разработчик на Python?

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

Убежден, что возвращение к основам для программиста всегда окупается, независимо от его уровня квалификации или опыта.

Нужно сказать, что я не сторонник того, что необходимо сосредоточиваться на расширении знаний об одних только структурах данных — проблема такого подхода заключается в том, что тогда мы застреваем в «стране грез» и не даем реальных результатов, пригодных для поставки клиентам…

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

Делаете ли вы это в течение нескольких дней в виде четко сформулированного «спринта» либо в виде затянувшегося проекта урывками тут и там, не имеет никакого значения. Так или иначе, обещаю, что время будет потрачено не напрасно.

Ладно, значит, структуры данных в Python, так? У нас есть списки, словари, множества… м-м-м. Стеки? Разве у нас есть стеки?

Видите ли, проблема в том, что Python поставляется с обширным набором структур данных, которые находятся в его стандартной библиотеке. Однако их обозначение иногда немного «уводит в сторону».

Зачастую неясно, как именно общеизвестные «абстрактные типы данных», такие как стек, соответствуют конкретной реализации на Python. Другие языки, например Java, больше придерживаются принципов «computer sciencе» и явной схемы именования: в Java список не просто «список» — это либо связный список LinkedList, либо динамический массив ArrayList.

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

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

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

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

Если вы ищете хорошую книгу, которая приведет в порядок ваши общие познания относительно структур данных, то я настоятельно рекомендую книгу Стивена С. Скиены «Алгоритмы: построение и анализ» (Steven S. Skiena’s, The Algorithm Design Manual).

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

5.1. Словари, ассоциативные массивы и хеш-таблицы

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

Словари также нередко называют ассоциативными массивами (associative arrays), ассоциативными хеш-таблицами (hashmaps), поисковыми таблицами (lookup tables) или таблицами преобразования. Они допускают эффективный поиск, вставку и удаление любого объекта, связанного с заданным ключом.

Что это означает на практике? Оказывается, что телефонные книги представляют собой достойный аналог объектов-словарей из реальной жизни:

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

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

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

Итак, каким же образом Python обращается со словарями?

Давайте отправимся на экскурсию по реализациям словаря, имеющимся в ядре Python и стандартной библиотеке Python.

dict — ваш дежурный словарь

Из-за своей важности Python содержит надежную реализацию словаря, которая встроена непосредственно в ядро языка: тип данных dict.

Для работы со словарями в своих программах Python также предоставляет немного полезного «синтаксического сахара». Например, синтаксис выражения с фигурными скобками для словаря и конструкция включения в словарь позволяют удобно определять новые объекты-словари:

phonebook = {

     'боб': 7387,

     'элис': 3719,

     'джек': 7052,

}

 

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

 

>>> phonebook['элис']

3719

>>> squares

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

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

Словари Python индексируются ключами, у которых может быть любой хешируемый тип: хешируемый объект имеет хеш-значение, которое никогда не меняется в течение его жизни (см. __hash__), и его можно сравнивать с другими объектами (см. __eq__). Кроме того, эквивалентные друг другу хешируемые объекты должны иметь одинаковое хеш-значение.

Неизменяемые типы, такие как строковые значение и числа, являются хешируемыми объектами и хорошо работают в качестве ключей словаря. В качестве ключей словаря также можно использовать объекты-кортежи — при условии, что они сами содержат только хешируемые типы.

Для большинства вариантов использования встроенная в Python реализация словаря делает все, что вам нужно. Словари хорошо оптимизированы и лежат в основе многих частей языка: например, и атрибуты класса, и переменные в стековом фрейме во внутреннем представлении хранятся в словарях.

Словари Python основаны на хорошо протестированной и тонко настроенной реализации хеш-таблицы, которая обеспечивает ожидаемые характеристики производительности с временной сложностью O(1) для операций поиска, вставки, обновления и удаления в среднем случае.

Нет особых причин не использовать стандартную реализацию dict, включенную в Python. Тем не менее существуют специализированные сторонние реализации словаря, например списки с пропусками или словари на основе B-деревьев.

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

Давайте их рассмотрим.

collections.OrderedDict — помнят порядок вставки ключей

В Python включен специализированный подкласс dict, который запоминает порядок вставки добавляемых в него ключей: collections.OrderedDict.

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

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

>>> import collections

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

>>> d

OrderedDict([('один', 1), ('два', 2), ('три', 3)])

 

>>> d['четыре'] = 4

>>> d

OrderedDict([('один', 1), ('два', 2),

             ('три', 3), ('четыре', 4)])

 

>>> d.keys()

odict_keys(['один', 'два', 'три', 'четыре'])

collections.defaultdict — возвращает значения, заданные по умолчанию для отсутствующих ключей

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

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

>>> from collections import defaultdict

>>> dd = defaultdict(list)

# Попытка доступа к отсутствующему ключу его создает и

# инициализирует, используя принятую по умолчанию фабрику,

# то есть в данном примере list():

>>> dd['собаки'].append('Руфус')

>>> dd['собаки'].append('Кэтрин')

>>> dd['собаки'].append('Сниф')

>>> dd['собаки']

['Руфус', 'Кэтрин', 'Сниф']

collections.ChainMap — производит поиск в многочисленных словарях как в одной таблице соответствия

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

>>> from collections import ChainMap

>>> dict1 = {'один': 1, 'два': 2}

>>> dict2 = {'три': 3, 'четыре': 4}

>>> chain = ChainMap(dict1, dict2)

>>> chain

ChainMap({'один': 1, 'два': 2}, {'три': 3, 'четыре': 4})

 

# ChainMap выполняет поиск в каждой коллекции в цепочке

# слева направо, пока не найдет ключ (или не потерпит неудачу):

>>> chain['три']

3

>>> chain['один']

1

>>> chain['отсутствует']

KeyError: 'отсутствует'

types.MappingProxyType — обертка для создания словарей только для чтения

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

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

>>> from types import MappingProxyType

>>> writable = {'один': 1, 'два': 2}  # доступный для обновления

>>> read_only = MappingProxyType(writable)

 

# Этот представитель/прокси с доступом только для чтения:

>>> read_only['один']

1

>>> read_only['один'] = 23

TypeError:

"'mappingproxy' object does not support item assignment"

 

# Обновления в оригинале отражаются в прокси:

>>> writable['один'] = 42

>>> read_only

mappingproxy({'один': 42, 'один': 2})

Словари в Python: заключение

Все перечисленные в этом разделе питоновские реализации словаря ­являются действующими, они встроены в стандартную библиотеку Python.

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

Я порекомендовал бы использовать один из прочих перечисленных здесь типов данных, только если у вас есть особые требования, которые не могут быть обеспечены типом dict.

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

Ключевые выводы

• Словари — это единственная центральная структура данных в Python.

• Встроенный тип dict будет «вполне приемлем» в большинстве случаев.

• Специализированные реализации, такие как словари с доступом только для чтения или упорядоченные словари, имеются в стандартной библиотеке Python.

5.2. Массивоподобные структуры данных

Массив (array) — это фундаментальная структура данных, имеющаяся в большинстве языков программирования, и он имеет широкий спектр применений в самых разных алгоритмах.

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

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

Как работают массивы и для чего они применяются?

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

Поскольку массивы хранят информацию в смежных блоках памяти, их рассматривают как непрерывные (нефрагментированные) структуры данных (в противоположность связным структурам данных, таким как связные списки, например).

Аналогией из реального мира, соответствующей этой структуре данных, является автостоянка:

Автостоянку можно рассматривать как единое целое и как отдельный объект, но внутри автостоянки есть места для парковки, индексируемые по уникальному числу. Места для парковки являются контейнерами для транспортных средств — каждое место для парковки может либо быть пустым, либо содержать автомобиль, мотоцикл или другое транспортное средство, припаркованное там.

Но не все автостоянки одинаковые:

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

С точки зрения производительности поиск элемента, содержащегося в массиве, выполняется очень быстро при условии, что указан индекс элемента. Для данного случая надлежащая реализация массива гарантирует постоянное O(1) время доступа.

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

list — изменяемые динамические массивы

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

Списки Python могут содержать произвольные элементы — в Python абсолютно «всё» является объектом, включая и функции. Поэтому вы можете сочетать и комбинировать разные типы данных и хранить их все в одном списке.

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

>>> arr = ['один', 'два', 'три']

>>> arr[0]

'один'

 

# Списки имеют хороший метод repr:

>>> arr

['один', 'два', 'три']

 

# Списки могут изменяться:

>>> arr[1] = 'привет'

>>> arr

['один', 'привет', 'три']

 

>>> del arr[1]

>>> arr

['один', 'три']

 

# Списки могут содержать произвольные типы данных:

>>> arr.append(23)

>>> arr

['один', 'три', 23]

tuple — неизменяемые контейнеры

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

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

>>> arr = 'один', 'два', 'три'

>>> arr[0]

'one'

 

# Кортежи имеют хороший метод repr:

>>> arr ('один', 'два', 'три')

 

# Кортежи не могут изменяться:

>>> arr[1] = 'привет'

TypeError:

"'tuple' object does not support item assignment"

 

>>> del arr[1]

TypeError:

"'tuple' object doesn't support item deletion"

 

# Кортежи могут содержать произвольные типы данных:

# (При добавлении элементов создается копия кортежа)

>>> arr + (23,)

('один', 'два', 'три', 23)

array.array — элементарные типизированные массивы

Модуль Python array обеспечивает пространственно-эффективное хранение элементарных типов данных в стиле языка C, таких как байты, 32-разрядные целые числа, числа с плавающей точкой и т.д.

Массивы, создаваемые на основе класса array.array, могут изменяться и ведут себя аналогично спискам, за исключением одного важного различия — они являются «типизированными массивами», ограниченными единственным типом данных.

Из-за этого ограничения объекты array.array со многими элементами более пространственно эффективны, чем списки и кортежи. Хранящиеся в них элементы плотно упакованы, и это может быть полезно, если вам нужно хранить много элементов одного и того же типа.

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

>>> import array

>>> arr = array.array('f', (1.0, 1.5, 2.0, 2.5))

>>> arr[1]

1.5

 

# Массивы имеют хороший метод repr:

>>> arr

array('f', [1.0, 1.5, 2.0, 2.5])

 

# Массивы могут изменяться:

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

 

# Массивы — это "типизированные" структуры данных:

>>> arr[1] = 'привет'

TypeError: "must be real number, not str"

str — неизменяемые массивы символов Юникода

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

Строковые объекты пространственно эффективны, потому что они плотно упакованы и специализируются на одном-единственном типе данных. Если вы храните текст в кодировке Юникод, то лучше использовать этот тип данных. Поскольку строки в Python не могут изменяться, модификация строкового значения требует создания модифицированной копии. Самым близким эквивалентом «изменяющейся последовательности символов» будет список, в котором символы хранятся по отдельности.

>>> arr = 'abcd'

>>> arr[1]

'b'

>>> arr

'abcd'

 

# Строки неизменяемы:

>>> arr[1] = 'e'

TypeError:

"'str' object does not support item assignment"

 

>>> del arr[1]

TypeError:

"'str' object doesn't support item deletion"

 

# Строки могут быть распакованы в список, в результате чего

# они получают изменяемое представление:

>>> list('abcd')

['a', 'b', 'c', 'd']

>>> ''.join(list('abcd'))

'abcd'

 

# Строки — это рекурсивные структуры данных:

>>> type('abc')

"<class 'str'>"

>>> type('abc'[0])

"<class 'str'>"

bytes — неизменяемые массивы одиночных байтов

Объекты bytes представляют собой неизменяемые последовательности одиночных байтов (целых чисел в диапазоне 0 ≤ x ≤ 255). В концептуальном плане они подобны объектам str и их также можно представить как неизменяемые массивы байтов.

Аналогично строковому типу, тип bytes имеет свой собственный литеральный синтаксис, предназначенный для создания объектов, и объекты этого типа пространственно эффективны. Объекты bytes не могут изменяться, но, в отличие от строковых объектов, для «изменяемых массивов байтов» есть специальный тип данных, который называется bytearray, или байтовый массив, в который они могут быть распакованы. Вы узнаете о нем подробнее в следующем подразделе.

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

>>> arr[1]

1

 

# Байтовые литералы имеют свой собственный синтаксис:

>>> arr

b'x00x01x02x03'

>>> arr = b'x00x01x02x03'

 

# Разрешены только допустимые "байты":

>>> bytes((0, 300))

ValueError: "bytes must be in range(0, 256)"

 

# Байты неизменяемы:

>>> arr[1] = 23

TypeError:

"'bytes' object does not support item assignment"

 

>>> del arr[1]

TypeError:

"'bytes' object doesn't support item deletion"

bytearray — изменяемые массивы одиночных байтов

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

Объекты bytearray могут быть преобразованы обратно в неизменяемые объекты bytes, но это влечет за собой копирование абсолютно всех хранящихся в них данных — весьма медленная операция, занимающая O(n) времени.

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

>>> arr[1]

1

 

# Метод repr для bytearray:

>>> arr bytearray(b'x00x01x02x03')

 

# Байтовые массивы bytearray изменяемы:

>>> arr[1] = 23

>>> arr

bytearray(b'x00x17x02x03')

 

>>> arr[1]

23

 

# Байтовые массивы bytearray могут расти и сжиматься в размере:

>>> del arr[1]

>>> arr

bytearray(b'x00x02x03')

 

>>> arr.append(42)

>>> arr

bytearray(b'x00x02x03*')

 

# Байтовые массивы bytearray могут содержать только "байты"

# (целые числа в диапазоне 0 <= x <= 255)

>>> arr[1] = 'привет'

TypeError: "an integer is required"

 

>>> arr[1] = 300

ValueError: "byte must be in range(0, 256)"

 

# Bytearrays может быть преобразован в байтовые объекты:

# (Это скопирует данные)

>>> bytes(arr)

b'x00x02x03*'

Ключевые выводы

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

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

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

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

У вас есть числовые (целочисленные или с плавающей точкой) данные и для вас важны плотная упаковка и производительность? Попробуйте array.array и посмотрите, способен ли этот тип делать все, что вам нужно. Кроме того, рассмотрите выход за пределы стандартной библиотеки и попробуйте такие пакеты, как NumPy или Pandas.

У вас есть текстовые данные, представленные символами Юникода? Используйте встроенный в Python тип str. Если вам нужна «изменяемая последовательность символов», то используйте list как список символов.

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

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

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

5.3. Записи, структуры и объекты переноса данных

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

В этом разделе вы увидите, как реализовывать в Python записи, структуры и «старые добрые объекты данных» с использованием всего лишь встроенных типов данных и классов из стандартной библиотеки.

Кстати, здесь я использую определение понятия «запись» в широком смысле. Например, я также собираюсь обсудить такие типы, как встроенный в Python тип tuple, который может как считаться, так и не считаться записью в строгом смысле этого слова, потому что кортежи не обеспечивают именованные поля.

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

Ладно, давайте начнем!

dict — простые объекты данных

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

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

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

car1 = {

     'цвет': 'красный',

     'пробег': 3812.4,

     'автомат': True,

}

car2 = {

     'цвет': 'синий',

     'пробег': 40231,

     'автомат': False,

}

 

# Словари имеют хороший метод repr:

>>> car2

{'цвет': 'синий', 'автомат': False, 'пробег': 40231}

 

# Получить пробег:

>>> car2['пробег']

40231

 

# Словари изменяемы:

>>> car2['пробег'] = 12

>>> car2['лобовое стекло'] = 'треснутое'

>>> car2

{'лобовое стекло': 'треснутое', 'цвет': 'синий',

  'автомат': False, 'пробег': 12}

 

# Отсутствует защита от неправильных имен полей

# или отсутствующих/лишних полей:

car3 = {

    'цвет': 'зеленый',

    'автомат': False,

    'лобовое стекло': 'треснутое',

}

tuple — неизменяемые группы объектов

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

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

Как вы видите в приведенном ниже результате дизассемблирования байткода, конструирование кортежной константы занимает всего один код операции LOAD_CONST, в то время как конструирование объекта-списка с одинаковым содержимым требует еще нескольких операций:

>>> 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_CONS           1 ('a')

       6 LOAD_CONS           2 ('b')

       9 LOAD_CONST          3 ('c')

      12 BUILD_LIS           4

      15 RETURN_VALUE

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

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

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

А это — раздолье для ошибок «по недоразумению», например для разночтений порядка следования полей. Поэтому я рекомендую держать минимальное количество полей в кортеже.

# Поля: цвет, пробег, автомат

>>> car1 = ('красный', 3812.4, True)

>>> car2 = ('синий', 40231.0, False)

 

# Экземпляры кортежа имеют хороший метод repr:

>>> car1

('красный', 3812.4, True)

>>> car2

('синий', 40231.0, False)

# Получить пробег:

>>> car2[1]

40231.0

 

# Кортежи неизменяемы:

>>> car2[1] = 12

TypeError:

"'tuple' object does not support item assignment"

 

# Нет защиты от неверных имен полей

# или отсутствующих/лишних полей:

>>> car3 = (3431.5, 'зеленый', True, 'серебряный')

Написание собственного класса — больше работы, больше контроля

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

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

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

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

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

class Car:

     def __init__(self, color, mileage, automatic):

         self.color = color

         self.mileage = mileage

         self.automatic = automatic

 

>>> car1 = Car('красный', 3812.4, True)

>>> car2 = Car('синий', 40231.0, False)

 

# Получить пробег:

>>> car2.mileage

40231.0

 

# Классы изменяемы:

>>> car2.mileage = 12

>>> car2.windshield = 'треснутое'

 

# Строковое представление не очень полезно

# (приходится добавлять написанный вручную метод __repr__):

>>> car1

<Car object at 0x1081e69e8>

collections.namedtuple — удобные объекты данных

Класс namedtuple, доступный в Python 2.6+, предоставляет расширение встроенного типа данных tuple. Аналогично определению собственного класса, применение именованного кортежа namedtuple позволяет определять «шаблоны» многократного использования для своих записей, гарантирующие использование правильных имен полей.

Именованные кортежи неизменяемы, как и обычные кортежи. Это означает, что вы не можете добавлять новые поля или изменять существующие поля после того, как экземпляр namedtuple был создан.

Помимо этого, именованные кортежи являются, скажем так, именованными кортежами (named tuples). Доступ к каждому хранящемуся в них объекту можно получить по уникальному идентификатору. Это освобождает от необходимости запоминать целочисленные индексы или идти обходными методами, например определять индексы целочисленных констант в качестве мнемокодов.

На внутреннем уровне объекты 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)

72

>>> getsizeof(p2)

72

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

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

Использование именованных кортежей вместо неструктурированных кортежей и словарей может облегчить жизнь и моим коллегам, потому что именованные кортежи позволяют раздавать данные в «самодокументированном» виде (в известной степени).

>>> from collections import namedtuple

>>> Car = namedtuple('Авто' , 'цвет пробег автомат')

>>> car1 = Car('красный', 3812.4, True)

 

# Экземпляры имеют хороший метод repr:

>>> car1 Авто(цвет='красный', пробег=3812.4, автомат=True)

 

# Доступ к полям:

>>> car1.пробег

3812.4

 

# Поля неизменяемы:

>>> car1.пробег = 12

AttributeError: "can't set attribute"

>>> car1.лобовое_стекло = 'треснутое'

AttributeError:

"'Car' object has no attribute 'лобовое_стекло'"

typing.NamedTuple — усовершенствованные именованные кортежи

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

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

>>> from typing import NamedTuple

class Car(NamedTuple):

     цвет: str

     пробег: float

     автомат: bool

>>> car1 = Car('красный', 3812.4, True)

# Экземпляры имеют хороший метод repr:

>>> car1 Car(цвет='красный', пробег=3812.4, автомат=True)

# Доступ к полям:

>>> car1.пробег 3812.4

 

# Поля неизменяемы:

>>> car1.пробег = 12

AttributeError: "can't set attribute"

>>> car1.лобовое_стекло = 'треснутое'

AttributeError:

"'Car' object has no attribute 'лобовое_стекло'"

 

# Аннотации типа не поддерживаются без отдельного  

# инструмента проверки типов, такого как mypy:

>>> Car('красный', 'НЕВЕЩЕСТВЕННЫЙ', 99)

Car(цвет='красный', пробег='НЕВЕЩЕСТВЕННЫЙ', автомат=99)

struct.Struct — сериализованные С-структуры

Класс struct.Struct выполняет преобразование между значениями Python и структурами C, сериализованными в форму объектов Python bytes. Например, он может использоваться для обработки двоичных данных, хранящихся в файлах или поступающих из сетевых соединений.

Структуры Struct определяются с использованием форматного строкоподобного мини-языка, который позволяет определять расположение различных типов данных C, таких как char, int и long, а также их беззнаковых вариантов.

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

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

>>> from struct import Struct

>>> MyStruct = Struct('i?f')

>>> data = MyStruct.pack(23, False, 42.0)

 

# Вы получаете двоичный объект данных (blob):

>>> data

b'x17x00x00x00x00x00x00x00x00x00(B'

 

# BLOB-объекты можно снова распаковать:

>>> MyStruct.unpack(data)

(23, False, 42.0)

types.SimpleNamespace — причудливый атрибутивный доступ

А вот еще один «эзотерический» вариант реализации объектов данных в Python: types.SimpleNamespace. Этот класс был добавлен в Python 3.3, и он обеспечивает атрибутивный доступ к своему пространству имен.

Это означает, что экземпляры SimpleNamespace показывают все свои ключи как атрибуты класса. А значит, вы можете использовать «точечный» атрибутивный доступ объект.ключ вместо синтаксиса с индексацией в квадратных скобках объект['ключ'], который применяется обычными словарями. Все экземпляры также по умолчанию включают содержательный метод __repr__.

Как видно из его названия, тип SimpleNamespace прост в использовании! Это, в сущности, прославленный словарь, который предоставляет доступ по атрибуту и выдает приличную распечатку. Атрибуты могут свободно добавляться, изменяться и удаляться.

>>> from types import SimpleNamespace

>>> car1 = SimpleNamespace(цвет='красный',

...                       пробег=3812.4,

...                       автомат=True)

 

# Метод repr по умолчанию:

>>> car1

namespace(автомат=True, пробег=3812.4, цвет='красный')

 

# Экземпляры поддерживают атрибутивный доступ и могут изменяться:

>>> car1.пробег = 12

>>> car1.лобовое_стекло = 'треснутое'

>>> del car1.автомат

>>> car1

namespace(лобовое_стекло='треснутое', пробег=12, цвет='красный')

Ключевые выводы

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

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

Вам нужны неизменяемые поля: в данном случае обыкновенные кортежи, collections.namedtuple и typing.NamedTuple, дадут неплохие возможности для реализации этого типа объекта данных.

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

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

Вам нужен полный контроль над вашей структурой данных: самое время написать собственный класс с методами-модификаторами (сеттерами) и методами-получателями (геттерами) @property.

Вам нужно добавить в объект поведение (методы): вам следует написать собственный класс с нуля либо путем расширения collections.namedtuple или typing.NamedTuple.

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

Если вы ищете безопасный вариант, который можно использовать по умолчанию, то моя общая рекомендация в отношении реализации простой записи, структуры или объекта данных в Python будет следующей: использовать collections.namedtuple в Python 2.x и его младшего брата, typing.NamedTuple, в Python 3.

5.4. Множества и мультимножества

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

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

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

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

vowels = {'a', 'e', 'i', 'o', 'u'}

squares = {x * x for x in range(10)}

Тем не менее следует быть осторожными: для того чтобы создать пустое множество, вам нужно вызвать конструктор set(). Использование фигурных скобок {} неоднозначно и вместо этого создаст пустой словарь.

Python и его стандартная библиотека предоставляют несколько реализаций множества. Давайте их рассмотрим.

set — ваше дежурное множество

Это встроенная в Python реализация множества. Тип set изменяемый и допускает динамическую вставку и удаление элементов.

Множества Python set подкрепляются типом данных dict и обладают одинаковыми характеристиками производительности. Любой хешируемый объект может храниться в множестве set.

>>> vowels = {'а', 'о', 'э', 'и', 'у', 'ы', 'е', 'е', 'ю', 'я'}

>>> 'э' in vowels

True

 

>>> letters = set('алиса')

>>> letters.intersection(vowels)

{'а', 'и'}

 

>>> vowels.add('х')

>>> vowels

{'х', 'о', 'э', 'у', 'и', 'ы', 'е', 'е', 'ю', 'а', 'я'}

 

>>> len(vowels)

6

frozenset — неизменяемые множества

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

>>> vowels = frozenset({'а', 'о', 'э', 'и', 'у', 'ы', 'е', 'е', 'ю',

                        'я'}) >>> vowels.add('р')

AttributeError:

"'frozenset' object has no attribute 'add'"

 

# Множества frozenset хешируемы и могут

# использоваться в качестве ключей словаря:

>>> d = { frozenset({1, 2, 3}): 'привет' }

>>> d[frozenset({1, 2, 3})]

'привет'

collections.Counter — мультимножества

Класс collections.Counter стандартной библиотеки Python реализует тип «мультимножество» (или «мешок»), который допускает неоднократное появление элемента в множестве.

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

>>> from collections import Counter

>>> inventory = Counter()

 

>>> loot = {'клинок': 1, 'хлеб': 3}

>>> inventory.update(loot)

>>> inventory

Counter({'клинок': 1, 'хлеб': 3})

 

>>> more_loot = {'клинок': 1, 'яблоко': 1}

>>> inventory.update(more_loot)

>>> inventory

Counter({'клинок': 2, 'хлеб': 3, 'яблоко': 1})

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

>>> len(inventory)

3 # Количество уникальных элементов

>>> sum(inventory.values())

6 # Общее количество элементов

Ключевые выводы

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

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

• Объекты frozenset хешируемы и могут использоваться в качестве словаря или ключей множества.

• Класс collections.Counter реализует структуры данных «мультимножество», или «мешок».

5.5. Стеки (с дисциплиной доступа LIFO)

Стек представляет собой коллекцию объектов, которая поддерживает быструю семантику доступа «последним пришел — первым ушел» (LIFO — last in, first out) для вставок и удалений. В отличие от списков или множеств, стеки, как правило, не допускают произвольного доступа к объектам, которые они содержат. Операции вставки и удаления также нередко называются вталкиванием (push) и выталкиванием (pop).

Полезной аналогией для стековой структуры данных из реального мира является стопка тарелок:

Новые тарелки добавляются на вершину стопки. И поскольку тарелки дорогие и тяжелые, можно взять только самую верхнюю тарелку (метод «последним пришел — первым ушел»). Чтобы добраться до тарелок, которые находятся внизу стопки, необходимо поочередно удалить все тарелки, которые находятся выше.

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

В случае с очередью вы удаляете элемент, который был добавлен в нее раньше всех (метод «первым пришел — первым ушел», или FIFO); однако в случае со стеком вы удаляете элемент, который был добавлен в него позже всех (метод «последним пришел — первым ушел», или LIFO).

С точки зрения производительности предполагается, что надлежащая реализация стека будет занимать O(1) времени на операции вставки и удаления.

Стеки находят широкое применение в алгоритмах, например в синтаксическом анализе языка и управлении рабочей памятью времени исполнения («стек вызовов»). Короткий и красивый алгоритм с использованием стека представлен поиском в глубину (DFS) на древовидной или графовой структуре данных.

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

list — простые встроенные стеки

Встроенный в Python тип list создает нормальную стековую структуру данных, поскольку он поддерживает операции вталкивания и выталкивания за амортизируемое O(1) время.

На внутреннем уровне списки Python реализованы как динамические массивы, а значит, при добавлении или удалении элементов им время от времени нужно изменять пространство оперативной памяти для хранящихся в них элементов. Список выделяет избыточную резервную память, с тем чтобы не каждая операция вталкивания и выталкивания требовала изменения размера памяти, и, как результат, для этих операций вы получаете амортизируемую временную сложность O(1).

Недостаток же состоит в том, что это делает показатели их производительности менее надежными, чем стабильные вставки и удаления с временной сложностью O(1), которые обеспечиваются реализацией на основе связного списка (такого, как collections.deque, см. ниже). С другой стороны, списки реально обеспечивают быстрый (со временем O(1)) произвольный доступ к элементам в стеке, и это может быть дополнительным преимуществом.

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

Чтобы получить производительность с амортизируемым временем O(1) для вставок и удалений, новые элементы должны добавляться в конец списка методом append() и снова удалятся из конца методом pop(). Для оптимальной производительности стеки на основе списков Python должны расти по направлению к более высоким индексам и сжиматься к более низким.

Добавление и удаление элементов в начале списка намного медленнее и занимает O(n) времени, поскольку существующие элементы должны сдвигаться, чтобы создать место для нового элемента. Такого антишаблона производительности следует избегать.

>>> s = []

>>> s.append('есть')

>>> s.append('спать')

>>> s.append('программировать')

 

>>> s

['есть', 'спать', 'программировать']

 

>>> s.pop()

'программировать'

>>> s.pop()

'спать'

>>> s.pop()

'есть'

 

>>> s.pop()

IndexError: "pop from empty list"

collections.deque — быстрые и надежные стеки

Класс deque реализует очередь с двусторонним доступом, которая поддерживает добавление и удаление элементов с любого конца за O(1) (неамортизируемое) время. Поскольку двусторонние очереди одинаково хорошо поддерживают добавление и удаление элементов с любого конца, они могут служить и в качестве очередей, и в качестве стеков.

Объекты Python deque реализованы как двунаправленные связные списки, что дает им стабильную производительность для операций вставки и удаления элементов, но при этом плохую O(n) производительность для произвольного доступа к элементам в середине очереди.

В целом двусторонняя очередь collections.deque – отличный выбор, если вы ищете стековую структуру данных в стандартной библиотеке Python, которая обладает характеристиками производительности, аналогичными реализации на основе связного списка.

>>> from collections import deque

>>> s = deque()

>>> s.append('есть')

>>> s.append('спать')

 

>>> s.append('программировать')

>>> s

deque(['есть', 'спать', 'программировать'])

 

>>> s.pop()

'программировать'

 

>>> s.pop()

'спать'

 

>>> s.pop()

'есть'

 

>>> s.pop()

IndexError: "pop from an empty deque"

deque.LifoQueue — семантика блокирования для параллельных вычислений

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

Помимо LifoQueue, модуль queue содержит несколько других классов, которые реализуют очереди с мультипроизводителями/мультипотребителями, широко используемые в параллельных вычислениях.

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

>>> from queue import LifoQueue

>>> s = LifoQueue()

>>> s.put('есть')

>>> s.put('спать')

>>> s.put('программировать')

 

>>> s

<queue.LifoQueue object at 0x108298dd8>

>>> s.get()

'программировать'

 

>>> s.get()

'спать'

 

>>> s.get()

'есть'

 

>>> s.get_nowait()

queue.Empty

 

>>> s.get()

# Блокирует / ожидает бесконечно...

Сравнение реализаций стека в Python

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

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

• Список list поддерживается динамическим массивом, который делает его отличным выбором для быстрого произвольного доступа, но при этом требует нерегулярного изменения размеров во время добавления или удаления элементов. Список выделяет излишнюю резервную память, чтобы не каждая операция вталкивания и выталкивания требовала изменения размеров, и для этих операций вы получаете амортизируемую временную сложность O(1). Однако вам следует быть внимательными и стараться выполнять вставку и удаление элементов «с правильной стороны», используя методы append() и pop(). В противном случае производительность замедлится до O(n).

• Двусторонняя очередь collections.deque поддерживается двунаправленным связным списком, который оптимизирует добавления и удаления с обоих концов и обеспечивает для этих операций стабильную производительность O(1). Производительность класса deque не только стабильнее, но его также легче использовать, потому что вам не приходится переживать по поводу добавления или удаления элементов «не с того конца».

Резюмируя, я полагаю, что двусторонняя очередь collections.deque представляет собой отличный вариант для реализации стека (очереди LIFO) на Python.

Ключевые выводы

• Python поставляется с несколькими реализациями стека, которые обладают слегка различающимися характеристиками производительности и особенностями использования.

• Двусторонняя очередь collections.deque обеспечивает безопасную и быструю реализацию стека общего пользования.

• Встроенный тип list может применяться в качестве стека, но следует соблюдать осторожность и добавлять и удалять элементы только при помощи методов append() и pop(), чтобы избежать замедления производительности.

5.6. Очереди (с дисциплиной доступа FIFO)

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

Очередь представляет собой коллекцию объектов, которая поддерживает быструю семантику доступа «первым пришел — первым ушел» (FIFO — first in, first out) для вставок и удалений. Операции вставки и удаления иногда называются поставить в очередь (enqueue) и убрать из очереди (dequeue). В отличие от списков или множеств, очереди, как правило, не допускают произвольного доступа к объектам, которые они содержат.

Ниже приведена аналогия для очереди с дисциплиной доступа «первым пришел — первым ушел» из реального мира:

Представьте очередь разработчиков-питонистов, ожидающих получения значка участника конференции в день регистрации на PyCon. По мере прибытия новых участников к месту проведения конференции они выстраиваются в очередь, «становясь в ее конец», чтобы получить свои значки. Удаление (обслуживание) происходит в начале очереди, когда разработчики получают свои значки и пакет с материалами и подарками конференции и покидают очередь.

Еще один способ запомнить особенности структуры данных очередь состоит в том, чтобы представить ее как конвейер:

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

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

В случае с очередью вы удаляете элемент, который был добавлен в нее раньше всех (принцип «первым пришел — первым ушел», или FIFO); однако в случае со стеком вы удаляете элемент, который был добавлен в него позже всех (принцип «последним пришел — первым ушел», или LIFO).

С точки зрения производительности предполагается, что надлежащая ­реализация очереди будет занимать O(1) времени на операции вставки и удаления. Эти две выполняемые с очередью операции являются главными, и при правильной реализации они обеспечивают высокое быстродействие.

Очереди находят широкое применение в алгоритмах и нередко помогают решать задачи планирования и параллельного программирования. Короткий и красивый алгоритм с использованием очереди представлен поиском в ширину (breadth-first search, BFS) на древовидной или графовой структуре данных.

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

Однако в обычной очереди содержащиеся в ней элементы не переупорядочиваются. Точно так же, как и в примере с конвейером, «вы получите только то, что вы вставили», и именно в таком порядке.

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

list — ужасно меееедленная очередь

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

Поэтому я не рекомендую использовать список в качестве импровизированной очереди в Python (если только вы не имеете дело с небольшим количеством элементов).

>>> q = []

>>> q.append('есть')

>>> q.append('спать')

>>> q.append('программировать')

 

>>> q

['есть', 'спать', 'программировать']

 

# Осторожно: это очень медленная операция!

>>> q.pop(0)

'есть'

collections.deque — быстрые и надежные очереди

Класс deque реализует очередь с двусторонним доступом, которая поддерживает добавление и удаление элементов с любого конца за O(1) (неамортизируемое) время. Поскольку двусторонние очереди одинаково хорошо поддерживают добавление и удаление элементов с любого конца, они могут служить в качестве очередей и в качестве стеков.

Объекты Python deque реализованы как двунаправленные связные списки (doubly-linked lists). Это придает им превосходную и стабильную производительность для операций вставки и удаления элементов, но при этом плохую O(n) производительность для произвольного доступа к элементам в середине очереди.

Как результат, двусторонняя очередь collections.deque будет хорошим выбором, если вы ищете структуру данных очередь в стандартной библио­теке Python.

>>> from collections import deque

>>> q = deque()

>>> q.append('есть')

>>> q.append('спать')

>>> q.append('программировать')

 

>>> q

deque(['есть', 'спать', 'программировать'])

 

>>> q.popleft()

'есть'

 

>>> q.popleft()

'спать'

 

>>> q.popleft()

'программировать'

 

>>> q.popleft()

IndexError: "pop from an empty deque"

queue.Queue — семантика блокирования для параллельных вычислений

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

Модуль queue содержит несколько других классов, которые реализуют очереди с мультипроизводителями/мультипотребителями, которые широко используются в параллельных вычислениях.

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

>>> from queue import Queue

>>> q = Queue()

>>> q.put('есть')

>>> q.put('спать')

>>> q.put('программировать')

 

>>> q

<queue.Queue object at 0x1070f5b38>

 

>>> q.get()

'есть'

 

>>> q.get()

'спать'

 

>>> q.get()

'программировать'

 

>>> q.get_nowait()

queue.Empty

 

>>> q.get()

# Блокирует / ожидает бесконечно...

multiprocessing.Queue — очереди совместных заданий

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

В качестве специализированной реализации очереди, предназначенной для обмена данными между процессами, очередь multiprocessing.Queue упрощает распределение работы по многочисленным процессам с целью преодоления ограничений GIL. Этот тип очереди может хранить и передавать любой консервируемый (модулем pickle) объект через границы процессов.

>>> from multiprocessing import Queue

>>> q = Queue()

>>> q.put('есть')

>>> q.put('спать')

>>> q.put('программировать')

 

>>> q

<multiprocessing.queues.Queue object at 0x1081c12b0>

 

>>> q.get()

'есть'

 

>>> q.get()

'спать'

 

>>> q.get()

'программировать'

 

>>> q.get()

# Блокирует / ожидает бесконечно...

Ключевые выводы

• Python содержит несколько реализаций очередей в качестве составной части ядра языка и его стандартной библиотеки.

• Объекты-списки list могут использоваться в качестве очередей, но это обычно не рекомендуется делать из-за низкой производительности.

• Если вы не ищете поддержку параллельной обработки, то реализация, предлагаемая очередью collections.deque, является превосходным вариантом по умолчанию для реализации в Python структуры данных с дисциплиной доступа FIFO, то есть очереди. Она обеспечивает характеристики производительности, которые можно ожидать от хорошей реализации очереди, а также может применяться в качестве стека (очереди с дисциплиной доступа LIFO).

5.7. Очереди с приоритетом

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

Очередь с приоритетом можно представить как видоизмененную очередь: вместо получения следующего элемента по времени вставки она получает элемент с самым высоким приоритетом. Приоритет отдельных элементов определяется примененным к их ключам упорядочением.

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

Представьте работу планировщика задач операционной системы:

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

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

list — поддержание сортируемой очереди вручную

Вы можете использовать сортированный список list, который позволяет быстро идентифицировать и удалять наименьший или наибольший элемент. Недостатком является то, что вставка новых элементов в список является медленной O(n) операцией.

Несмотря на то что точка вставки может быть найдена за O(log n) время с помощью алгоритма bisect.insort стандартной библиотеки, это решение всегда находится во власти медленного шага вставки.

Поддержание упорядоченности путем добавления в конец списка и пересортировки также занимает минимум O(n log n) времени. Еще один недостаток — вам придется вручную заботиться о пересортировке списка во время вставки новых элементов. Пропустив этот шаг, можно легко внести ошибки, и ответственность за них всегда будет на вас как на разработчике.

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

q = []

 

q.append((2, 'программировать'))

q.append((1, 'есть'))

q.append((3, 'спать'))

 

# ПРИМЕЧАНИЕ: Не забудьте выполнить пересортировку всякий раз,

#             когда добавляется новый элемент, либо используйте

#             bisect.insort().

q.sort(reverse=True)

while q:

     next_item = q.pop()

     print(next_item)

# Результат:

#   (1, 'есть')

#   (2, 'программировать')

#   (3, 'спать')

heapq — двоичные кучи на основе списка

Данная реализация двоичной кучи обычно подкрепляется обыкновенным списком, и она поддерживает вставку и извлечение наименьшего элемента за O(log n) время.

Этот модуль — хороший выбор для реализации очередей с приоритетом в Python. Поскольку двоичная куча heapq технически обеспечивает только реализацию min-heap (то есть кучи, где значение в любой вершине не больше, чем значения ее потомков), должны быть предприняты дополнительные шаги, которые обеспечат стабильность сортировки и другие функциональные возможности, которые, как правило, ожидают от «практической версии» очереди с приоритетом.

import heapq

 

q = []

 

heapq.heappush(q, (2, 'программировать'))

heapq.heappush(q, (1, 'есть'))

heapq.heappush(q, (3, 'спать'))

 

while q:

     next_item = heapq.heappop(q)

     print(next_item)

 

# Результат:

#   (1, 'есть')

#   (2, 'программировать')

#   (3, 'спать')

queue.PriorityQueue — красивые очереди с приоритетом

Данная реализация очереди с приоритетом во внутреннем представлении использует двоичную кучу heapq и имеет одинаковую временную и пространственную вычислительную сложность.

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

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

from queue import PriorityQueue

 

q = PriorityQueue()

 

q.put((2, 'программировать'))

q.put((1, 'есть'))

q.put((3, 'спать'))

 

while not q.empty():

     next_item = q.get()

     print(next_item)

 

# Результат:

#   (1, 'есть')

#   (2, 'программировать')

#   (3, 'спать')

Ключевые выводы

• Python содержит несколько реализаций очередей с приоритетом, которые вы можете использовать в своих программах.

• Реализация queue.PriorityQueue выбивается из общего ряда, отличаясь хорошим объектно-ориентированным интерфейсом и именем, которое четко указывает на ее направленность. Такая реализация должна быть предпочтительным вариантом.

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