image_pdf

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

В Python словари (или «dicts» — ”дикты», для краткости) являются центральной структурой данных. Дикты хранят произвольное количество объектов, каждый из которых идентифицируется уникальным ключом. Словари часто называют картами, хэш-картами, таблицами поиска или ассоциативными массивами. Они позволяют осуществлять эффективный поиск, вставку, обновление и удаление любого объекта, связанного с данным ключом.

Более практичное объяснение — телефонные книги, которые являются достойным аналогом словарей из реального мира:

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

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

Словари Python, хэш-карты и хэш-таблицы

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

В Python есть полезные синтаксические «плюшки» для работы со словарями в своих программах. Например, использование фигурных скобок ({}) в синтаксисе описания словарей даёт чёткое понимание и позволяют удобно создавать новые словари:

phonebook = {
    'bob': 7387,
    'alice': 3719,
    'jack': 7052,
}

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

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

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

Встроенный тип данных dict

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

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

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

>>> phonebook = {'bob': 7387, 'alice': 3719, 'jack': 7052}
>>> phonebook['alice']
3719

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

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

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

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

Класс OrderedDict не встроен в основной язык и должен быть импортирован из модуля collections стандартной библиотеки.

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

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 — поиск нескольких словарей в одном представлении

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

>>> 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']
KeyError: 'missing'

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

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

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

>>> read_only['one']
1
>>> read_only['one'] = 23
TypeError: "'mappingproxy' object does not support item assignment"

Использование словарей в Python: заключение

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

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

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

Ознакомьтесь со статьёй «Фундаментальные структуры данных в Python» и серией статьй из рубрики «Фундаментальные структуры данных в Python».

В этой статье чего-то не хватает или вы нашли ошибку? Помогите коллеге и оставьте комментарий ниже.

Source

Опубликовано Вадим В. Костерин

Ст.преп. кафедры ИТЭ. Автор более 130 научных и учебно-методических работ. Лауреат ВДНХ (серебряная медаль).

Оставьте комментарий

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