Если вы знакомы с основами языка Python, вы должны знать, что в Python имеется встроенная поддержка множеств, как и стеков. Однако множества поддерживаются еще более непосредственным способом — тип данных set в Python предоставляет стандартный набор оптимизированных операций над множествами. Встроенный тип set достаточно прост в использовании: объекты множеств создаются обращением к имени типа set как к функции, которой передается итерируемый объект или последовательность компонентов для включения в множество, или выполнением выражения генератора множества:
> >> x = set(‘abcde‘) # из итерируемого объекта/последовательности
> >> y = {c for c in ‘bdxyz‘} # то же самое с помощью генератора множеств >>> x
{‘a‘, ‘c‘, ‘b‘, ‘e‘, ‘d‘}
> >> y
{‘y’, ‘x’, ‘b’, ‘d’, ‘z’}
После создания множества становятся доступными все обычные операции. Ниже демонстрируются наиболее типичные из них:
> >> ‘e’ in x # принадлежность
True
> >> x — у # разность
{‘a’, ‘c’, ‘e’}
> >> x & y # пересечение
{‘b’, ‘d’}
> >> x | y # объединение
{‘a’, ‘c’, ‘b’, ‘e’, ‘d’, ‘y’, ‘x’, ‘z’}
>>> x = set([‘spam‘, ‘ham‘, ‘eggs‘]) # последовательность неизменяемых элем.
>>> x
{‘eggs‘, ‘ham‘, ‘spam‘}
>>> x = {‘spam‘, ‘ham‘, ‘eggs‘} # литерал множества, если элементы известны
>>> x
{‘eggs‘, ‘ham‘, ‘spam‘}
>>> x = set([[‘spam‘, ‘ham‘], [‘eggs‘]]) # изменяемые элементы не могут TypeError: unhashable type: ‘list‘ # включаться в множество
>>> x = set({‘spam’:[1, 1], ‘ham’: [2, 2], ‘eggs’:[3, 3]})
>>> x
{‘eggs‘, ‘ham‘, ‘spam‘}
Существуют также другие операции, которые мы не будем описывать здесь, — подробности ищите в книгах, посвященных основам языка, в таких как «Изучаем Python». Например, встроенные множества поддерживают такие операции, как проверка на надмножество, и имеют две разновидности: изменяемые и фиксированные (фиксированные множества являются хешируемыми и могут использоваться для создания множества множеств). Кроме того, генераторы множеств обладают более широкими возможностями, чем показано здесь, и множества являются естественным инструментом удаления дубликатов:
> >> y = {c.upper() * 4 for c in ‘spamham’} # генератор множеств
> >> y
{‘SSSS’, ‘AAAA’, ‘MMMM’, ‘HHHH’, ‘PPPP’}
>>>
> >> list(set([1, 2, 3, 1, 2])) # удалит дубликаты из списка
[1, 2, 3]
Однако, как и в случае со стеками, встроенный тип set может не полностью удовлетворять наши потребности. Кроме того, собственная реализация множества может оказаться идеальным примером реализации нестандартных структур данных в языке Python. Хотя по своей производительности конечный результат может оказаться неконкурентоспособным в сравнении со встроенными множествами, тем не менее, попытка создать собственную реализацию может оказаться весьма поучительной и интересной.
Кроме того, подобно стекам наша собственная реализация множества будет опираться на использование других встроенных типов. Списки, кортежи и строки Python близки к понятию множества: оператор in проверяет принадлежность, for производит итерации и так далее. Здесь мы введем операции, не поддерживаемые непосредственно последовательностями Python. Идея состоит в рас шире нии встроенных типов в соответствии с особыми требованиями.
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
