Б41 Чистый Python. Тонкости программирования для профи. Спб.: Питер

# Попытка доступа к отсутствующему ключу его создает и 
# инициализирует, используя принятую по умолчанию фабрику, 
# то есть в данном примере list(): 
>>> dd['собаки'].append('Руфус') 
>>> dd['собаки'].append('Кэтрин') 
1
См. документацию Python «collections.defaultdict»: 
https://docs .python .org/3/library/
collections .html#defaultdict-objects

---

5 .1 . Словари, ассоциативные массивы и хеш-таблицы 159
>>> dd['собаки'].append('Сниф')
>>> dd['собаки'] 
['Руфус', 'Кэтрин', 'Сниф']
collections .ChainMap — производит поиск в многочисленных 
словарях как в одной таблице соответствия
Структура данных 
collections.ChainMap
группирует многочисленные 
словари в одну таблицу соответствия
1
. Поиск проводится по очереди во 
всех базовых ассоциативных объектах до тех пор, пока ключ не будет 
найден. Операции вставки, обновления и удаления затрагивают только 
первую таблицу соответствия, добавленную в цепочку.
>>> 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
— это обертка стандартного словаря, которая предо-
ставляет доступ только для чтения данных обернутого словаря
2
. Этот 
1
См. документацию Python «collections.ChainMap»: 
https://docs .python .org/3/library/
collections .html#collections .ChainMap
2
См. документацию Python «types.MappingProxyType»: 
https://docs .python .org/3/library/
types .html

---

160 Глава 5 • Общие структуры данных Python
класс был добавлен в 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
.

---

5 .2 . Массивоподобные структуры данных 161
Да, я по-прежнему убежден, что все эти варианты допустимы, но, как 
правило, в большинстве случаев ваш исходный код будет яснее и легче 
в сопровождении для других разработчиков, если он будет опираться на 
стандартные словари Python.
Ключевые выводы
‰
‰
Словари — это единственная центральная структура данных в Python.
‰
‰
Встроенный тип 
dict
будет «вполне приемлем» в большинстве случаев.
‰
‰
Специализированные реализации, такие как словари с доступом толь-
ко для чтения или упорядоченные словари, имеются в стандартной 
библиотеке Python.
5 .2 . Массивоподобные структуры данных
Массив (array) — это фундаментальная структура данных, имеющаяся 
в большинстве языков программирования, и он имеет широкий спектр 
применений в самых разных алгоритмах.
В этом разделе мы рассмотрим реализации массива в Python, в кото-
рых используются только базовые функциональные средства языка 
или функциональность, которая включена в стандартную библиотеку 
Python.
Вы увидите достоинства и недостатки каждого подхода, благодаря чему 
сможете решить, какая реализация подходит для вашего варианта исполь-
зования. Но прежде чем начать, рассмотрим некоторые основы.
Как работают массивы и для чего они применяются?
Массивы состоят из записей данных, при этом записи имеют фиксиро-
ванный размер, что позволяет эффективно размещать каждый элемент 
на основе его индекса.
Поскольку массивы хранят информацию в смежных блоках памяти, их 
рассматривают как непрерывные (нефрагментированные) структуры 

---

162 Глава 5 • Общие структуры данных Python
данных (в противоположность связным структурам данных, таким как 
связные списки, например).
Аналогией из реального мира, соответствующей этой структуре данных, 
является автостоянка:
Автостоянку можно рассматривать как единое целое и как отдельный 
объект, но внутри автостоянки есть места для парковки, индексируемые 
по уникальному числу . Места для парковки являются контейнерами для 
транспортных средств — каждое место для парковки может либо быть 
пустым, либо содержать автомобиль, мотоцикл или другое транспортное 
средство, припаркованное там .
Но не все автостоянки одинаковые:
Некоторые автостоянки могут быть ограничены только одним типом 
транспортного средства . Например, на кемпинговой автостоянке не раз-
решено парковать велосипеды . «Ограниченная» автостоянка соответ-
ствует структуре данных для «типизированного массива», которая допу-
скает только те элементы, которые имеют одинаковый тип хранящихся 
в них данных .
С точки зрения производительности поиск элемента, содержащегося 
в массиве, выполняется очень быстро при условии, что указан индекс эле-
мента. Для данного случая надлежащая реализация массива гарантирует 
постоянное O(1) время доступа.
В своей стандартной библиотеке Python содержит несколько массивопо-
добных структур данных, каждая из которых обладает слегка отличающи-
мися характеристиками. Давайте их рассмотрим.
list — изменяемые динамические массивы
Списки (lists) являются составной частью ядра языка Python
1
. Несмотря 
на свое имя, списки Python реализованы как динамические массивы. Это 
означает, что список допускает добавление и удаление элементов и авто-
1
См. документацию Python «list»: 
https://docs .python .org/3/tutorial/introduction .html#lists
и 
https://docs .python .org/3/tutorial/datastructures .html#more-on-lists

---

5 .2 . Массивоподобные структуры данных 163
матически корректирует резервное хранилище, в котором эти элементы 
содержатся, путем выделения или высвобождения оперативной памяти.
Списки Python могут содержать произвольные элементы — в Python 
абсолютно «всё» является объектом, включая и функции. Поэтому вы 
можете сочетать и комбинировать разные типы данных и хранить их все 
в одном списке.
Такая возможность может быть очень мощной, но у нее есть и обратная 
сторона: поддержка многочисленных типов данных одновременно озна-
чает, что данные, как правило, упакованы менее плотно. И в результате 
вся структура занимает больше места.
>>> arr = ['один', 'два', 'три'] 
>>> arr[0]