image_pdf

Как реализовать изменяемые и неизменяемые структуры данных set и multiset (bag) в Python, используя встроенные типы данных и классы из стандартной библиотеки?

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

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

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

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

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

Python и стандартная библиотека предоставляют следующие реализации набора:

Встроенный тип данных 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

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

>>> vowels = frozenset({'a', 'e', 'i', 'o', 'u'})
>>> vowels.add('p')
AttributeError: "'frozenset' object has no attribute 'add'"

Класс 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. Вызов len() возвращает количество уникальных элементов в multiset, в то время как общее количество элементов необходимо подсчитывать немного иначе:

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

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

Source

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

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

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

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