# Глава 14. Множества и неизменяемые множества
Для работы со множествами уникальных элементов в питоне реализован тип `set` и его неизменяемая версия `frozenset`. Давайте посмотрим, на что способны `set` и `frozenset`, а также за счет чего достигается их производительность.
## Объекты, которые можно хранить в set, frozenset и dict
В качестве ключей в коллекциях `set`, `frozenset` и `dict` ([словарь,](/courses/python/chapters/python_chapter_0150/) отображение для хранения пар ключ-значение) разрешается вперемешку хранить строки, числа, кортежи, другие объекты... Лишь бы они были хешируемыми.
**Хешируемый** объект в питоне — это объект, удовлетворяющий условиям: {#block-hash}
- От него можно вычислить хеш-значение, **неизменное** за все время жизни объекта.
- К объекту применим оператор сравнения `==`.
Как же узнать, какой объект хешируемый, а какой — нет? Для проверки достаточно применить к нему встроенную функцию `hash()`:
```python {.example_for_playground}
print(hash("some string"))
print(hash(["some", "list"]))
```
```
-8951052346672417576
TypeError: unhashable type: 'list'
```
Хеш от строки вернет целое число, а попытка вызова `hash()` от списка завершится ошибкой. Поэтому `str` относится к хешируемым типам, а `list` — нет.
Изменяемые встроенные типы не являются хешируемыми: вызов `hash()` от словаря, списка или множества приведет к исключению. Неизменяемые коллекции (такие как кортежи) **могут** быть хешируемыми, но только если свойство хешируемости применимо ко всем их элементам.
Пользовательские классы по умолчанию считаются хешируемыми: хеш для них вычисляется по id объекта, а оператор `==` сравнивает ссылки на области в памяти (то есть работает по принципу оператора `is`). Это поведение можно переопределить: работу с пользовательскими типами мы обсудим в следующих главах.
Уберите из кортежа все не хешируемые элементы, чтобы функция `hash()` отработала без ошибки. {.task_text}
```python {.task_source #python_chapter_0140_task_0010}
tpl = (None, -2, False, 145.5, (2, 4, 8), [2, 4, 8], "wednesday", set("set constructor"), dict())
print(hash(tpl))
```
Список, множество и словарь не являются хэшируемыми. {.task_hint}
```python {.task_answer}
tpl = (None, -2, False, 145.5, (2, 4, 8), "wednesday")
print(hash(tpl))
```
Итак, соблюдение свойства хешируемости позволяет хранить объект в коллекциях `set`, `frozenset`, `dict`. Эти коллекции имплементированы на базе хеш-таблиц [с открытой адресацией.](https://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0#%D0%9E%D1%82%D0%BA%D1%80%D1%8B%D1%82%D0%B0%D1%8F_%D0%B0%D0%B4%D1%80%D0%B5%D1%81%D0%B0%D1%86%D0%B8%D1%8F) Благодаря этому алгоритмическая сложность поиска, добавления и удаления элементов соответствует амортизированной константе O(1). {#block-complexity}
## Множества {#block-sets}
Множество (set) — это изменяемая неупорядоченная коллекция уникальных элементов. Тип `set` особенно незаменим, когда требуется:
- Поддерживать уникальность набора данных.
- Применять к данным математические операции из теории множеств: пересечение, объединение, разность, симметричная разность.
- Быстро проверять элемент на вхождение в множество.
## Создание множества {#block-create-set}
Для инициализации множества используется литерал фигурных скобок `{}` либо конструктор `set()`. Так выглядит инициализация через литерал:
```python {.example_for_playground}
web_frameworks = {"Django", "Flask", "FastAPI", "Flask"}
print(web_frameworks)
```
```
{'FastAPI', 'Flask', 'Django'}
```
В конструктор было передано 4 строки, но только 3 из них уникальны. Поэтому результирующее множество состоит из 3-х элементов.
Конструктор `set()` принимает на вход итерируемый объект. С его помощью легко получить множество из списка:
```python {.example_for_playground}
web_frameworks = set(["Django", "Flask", "FastAPI", "Flask"])
print(web_frameworks)
```
```
{'FastAPI', 'Flask', 'Django'}
```
...Из кортежа:
```python {.example_for_playground}
ml_libraries = set(("Pandas", "Pandas", "NumPy", "Keras", "TensorFlow"))
print(ml_libraries)
```
```
{'Pandas', 'Keras', 'NumPy', 'TensorFlow'}
```
...И из строки:
```python {.example_for_playground}
letters = set("AABBC")
print(letters)
```
```
{'A', 'C', 'B'}
```
Обратите внимание на элементы созданных в этих примерах множеств: они хранятся в произвольном порядке и среди них отсутствуют дубликаты.
Что насчет заведения пустого множества? С этой целью используйте **только** конструктор `set()`:
```python
vals = set()
```
Дело в том, что литерал `{}` также применяется и для создания [словарей](/courses/python/chapters/python_chapter_0150/) (контейнеров пар ключ-значение). Мы получаем некоторую двусмысленность при использовании **пустых** фигурных скобок: какой тип закрепится за объектом — множество или словарь? В соответствии с правилами языка будет создан словарь:
```python {.example_for_playground}
x = {}
print(type(x))
```
```
<class 'dict'>
```
Немного забегая вперед, посмотрим, как же выглядит инициализация не пустого словаря:
```python {.example_for_playground}
kv = {"key1": "val1", "key2": "val2"}
print(kv)
```
```
{'key1': 'val1', 'key2': 'val2'}
```
От правил инициализации множеств перейдем к основным операциям над ними.
## Операции над множествами
Как и к строкам, спискам и кортежам, к множествам применимы встроенная функция `len()` и оператор `in`. `len(a)` возвращает количество элементов множества `a`. Конструкция `x in a` позволяет узнать, входит ли элемент `x` в `a`.
Так же, как и для других коллекций, для типа `set` реализован обширный набор методов. Что любопытно, части из них соотнесены специальные операторы. Они помогают выразить то же самое в более компактной форме. Например, методу `a.intersection(b)` соответствует оператор `a & b`: он возвращает новое множество — пересечение `a` и `b`.
Имплементируйте функцию `print_set(obj)`. В качестве аргумента она принимает любой итерируемый объект: список, кортеж, строку и т.д. Функция на двух разных строках должна вывести в консоль множество, полученное из этого объекта, и размер множества.{.task_text}
```python {.task_source #python_chapter_0140_task_0020}
```
Размер множества `s`: `len(s)`. {.task_hint}
```python {.task_answer}
def print_set(obj):
s = set(obj)
print(s)
print(len(s))
```
Перечислим базовые [операции теории множеств,](https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2#%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D0%BD%D1%8F%D1%82%D0%B8%D1%8F) которые отражены методами класса `set` и специальными операторами.
**Пересечение:** возвращает элементы, которые входят в оба множества. Реализовано методом `a.intersection(b)` и оператором `a & b`. В обоих случаях можно искать пересечение неограниченного количества множеств, например: `a.intersection(b, c, d)`, что эквивалентно `a & b & c & d`.
**Объединение:** возвращает объединенное множество из всех элементов двух и более множеств. Для объединения множеств используется метод `a.union(b, c, d)` и оператор `a | b | c | d`.
**Разность:** возвращает элементы, которые есть в множестве `a`, но отсутствуют в `b`. Реализована методом `a.difference(b, c, d)` и оператором `a - b - c - d`. В отличие от пересечения и объединения разность не является симметричной: `a - b` и `b - a` вернут два разных набора элементов.
**Симметричная разность:** возвращает элементы, которые содержатся в любом из множеств, но не в их пересечении. Например, симметричная разность множеств `{1, 2, 3, 4}` и `{0, 4, 7}` — это `{0, 1, 2, 3, 7}`. В отличие от пересечения, объединения и разности, симметричная разность вычисляется только для пары множеств, но не большего их количества. Делается это с помощью метода `a.symmetric_difference(b)` и оператора `a ^ b`.
Замените комментарии на реальный код, задействующий операции над множествами.{.task_text}
```python {.task_source #python_chapter_0140_task_0030}
# Все доступные книги (находящиеся в продаже)
books_available = {"Fluent Python", "Python Cookbook", "Python crash course"}
# Уже купленные книги
books_purchased = {"Learning python", "Python in a nutshell", "Fluent Python"}
books_total = # Все доступные и приобретенные книги
books_popular = # Доступные книги, которые были куплены
books_sold_out = # Раскупленные книги, которых уже нет в продаже
```
Воспользуйтесь операциями объединения, пересечения и разности. {.task_hint}
```python {.task_answer}
# Все доступные книги (находящиеся в продаже)
books_available = {"Fluent Python", "Python Cookbook", "Python crash course"}
# Уже купленные книги
books_purchased = {"Learning python", "Python in a nutshell", "Fluent Python"}
books_total = books_available | books_purchased
books_popular = books_available & books_purchased
books_sold_out = books_purchased - books_available
```
Так выглядят основные способы **модификации** множеств:
- `a.add(x)` — добавляет элемент `x` в множество `a`.
- `a.update(b)` — добавляет все элементы из множества `b` в `a`. Количество аргументов метода `update()` не ограничено. Например, таким образом в `a` добавляются элементы из пяти множеств: `a.update(b, c, d, e, f)`. Вместо метода можно использовать оператор `|=`. Тогда добавление элементов из 5 множеств будет выглядеть так: `a |= b | c | d | e | f`.
- `a.remove(x)` — удаляет элемент `x` из множества `a`. Если такого элемента нет, генерирует исключение `KeyError`.
- `a.discard(x)` — удаляет элемент `x` из множества `a`, если он содержится в множестве. Если элемента нет, функция ничего не делает.
- `a.pop()` — удаляет и возвращает произвольный элемент множества. Если множество пустое, бросает исключение `KeyError`.
- `a.clear() ` — делает множество пустым: удаляет из него все элементы.
Реализуйте [вариативную функцию](/courses/python/chapters/python_chapter_0070#block-variadic) `avg_unique(*args)`, принимающую произвольное количество позиционных параметров - строк. Функция считает среднее арифметическое длин строк, причем каждая уникальная строка должна учитываться однократно. Для определения уникальности используйте множество. {.task_text}
Например, для строк `"Y", "Y", "TTT"` среднее арифметическое рассчитывается как (1 + 3) / 2, и функция возвращает результат 2.{.task_text}
```python {.task_source #python_chapter_0140_task_0040}
```
Создайте множество из входного списка. Проитерируйтесь по нему для расчета среднего арифметического. {.task_hint}
```python {.task_answer}
def avg_unique(*args):
l = 0
st = set(args)
if len(st) == 0:
return 0
for s in st:
l += len(s)
return l / len(st)
```
Также с помощью методов и операторов легко определять **соотношения множеств:**
- Является ли `a` подмножеством `b`: метод `a.issubset(b)` и операторы `a < b` и `a <= b` используются, чтобы понять, принадлежат ли все элементы одного множества другому (входит ли `a` в `b`). Оператор `a <= b` возвращает `True` также для случая, когда множества поэлементно совпадают.
- Является ли `a` супермножеством `b`: метод `a.issuperset(b)` и операторы `a > b` и `a >= b` нужны для проверки, что все элементы `b` входят в `a`. При выполнении условия `a > b` (`a` строго больше `b` и включает все его элементы) говорят, что `a` — чистое супермножество.
- Равны ли множества `a` и `b`: оператор `a == b` сравнивает два множества поэлементно.
Реализуйте функцию `analyze(a, b)`, которая принимает два множества и анализирует, как они соотносятся друг с другом: является ли `a` супермножеством над `b`, а также количество общих элементов `a` и `b`. Функция должна выводить в консоль отформатированную строку вида: {.task_text}
`a is b's superset: True/False. Count of common elements: N.` {.task_text}
Например, для множеств `{1, 2, 3}` и `{2, 3, 4}` функция выведет: {.task_text}
`a is b's superset: False. Count of common elements: 2.` {.task_text}
```python {.task_source #python_chapter_0140_task_0050}
```
Для определения, является ли `a` супермножеством `b`, воспользуйтесь оператором `>=`. Для определения количества общих элементов используйте `len(a & b)`. {.task_hint}
```python {.task_answer}
def analyze(a, b):
print(f"a is b's superset: {a >= b}. Count of common elements: {len(a & b)}.")
```
## Различия между методами класса set и операторами
При работе с множествами программист сам выбирает, как выразить ту или иную идею: через метод или через оператор. Но не во всех случаях метод и оператор поведут себя одинаково. В чем разница?
Методы, например `union()`, `difference()` и `issuperset()`, принимают в качестве аргумента любой итерабельный объект. А операторы ожидают только объекты типа `set`. Многие начинающие питонисты об этом забывают и надеются на автоматическое преобразование:
```python {.example_for_playground}
common_letters = set("abc") & "bcd"
```
В данном примере попытка найти пересечение между объектом-множеством и объектом-строкой закономерно завершится исключением:
```
TypeError: unsupported operand type(s) for &: 'set' and 'str'
```
Этот код должен выводить в консоль общие элементы между `"abc"` и `"bcd"`, но в нем допущена ошибка. Исправьте ее с помощью метода множества. {.task_text}
```python {.task_source #python_chapter_0140_task_0060}
common_letters = set("abc") & "bcd"
print(common_letters)
```
Требуется заменить оператор `&` на вызов метода `intersection()`. {.task_hint}
```python {.task_answer}
common_letters = set("abc").intersection("bcd")
```
## Неизменяемые множества {#block-frozensets}
`frozenset` — тип, с помощью которого создаются неизменяемые после инициализации множества. Он поддерживает тот же набор методов и операторов, что и `set`, за исключением направленных на модификацию. Более того, операторы допустимо использовать для сравнения содержимого множеств разных типов: `set` и `frozenset`.
```python {.example_for_playground}
a = frozenset("abc")
b = set("bcd")
intersection = a & b
print(intersection)
```
```
frozenset({'c', 'b'})
```
Применение оператора к операндам разных типов приводит к возврату объекта с типом первого операнда. Пример это подтверждает: оператор пересечения `&` вернул `frozenset`.
Также допустимо проверять `set` и `frozenset` на равенство через `==`: два множества сопоставляются поэлементно, и `==` возвращает `True` в случае полного совпадения элементов обоих множеств.
Объекты типа `frozenset` создаются только с помощью одноименного конструктора `frozenset()`, принимающего итерируемый объект.
Создайте переменную типа `frozenset` с именем `x` из списка `hashable_types`. Выведите ее в консоль. {.task_text}
```python {.task_source #python_chapter_0140_task_0070}
hashable_types = ["int", "frozenset", "bool", "int"]
```
Вызовите конструктор неизменяемого множества, передав в него список. {.task_hint}
```python {.task_answer}
hashable_types = ["int", "frozenset", "bool", "int"]
x = frozenset(hashable_types)
print(x)
```
Важное отличие `frozenset` от `set`: тип `frozenset` является **хешируемым.** А значит, может выступать в качестве ключа в `dict` или элемента в `set`.
В цикле пройдитесь по списку `objects`. Для каждого элемента выведите в консоль его тип и `True` либо `False` в зависимости от того, является ли тип объекта хешируемым. Например: {.task_text}
`<class 'set'> False` {.task_text}
Для проверки на хешируемость воспользуйтесь функцией `isinstance(object, class)`, которая определяет принадлежность объекта к интересующему классу. Первым аргументом передайте в нее объект, вторым — тип `typing.Hashable`. Он содержится в подключенном через ключевое слово `import` модуле `typing`.{.task_text}
```python {.task_source #python_chapter_0140_task_0080}
import typing
objects = ["M", 7.8, True, [9, 9], {1, 2, 2}, None, frozenset([5]), (True, False)]
```
Так выглядит проверка на хэшируемость: `isinstance(obj, typing.Hashable)`. {.task_hint}
```python {.task_answer}
import typing
objects = ["M", 7.8, True, [9, 9], {1, 2, 2}, None, frozenset([5]), (True, False)]
for obj in objects:
print(type(obj), isinstance(obj, typing.Hashable))
```
## Резюмируем
- Тип `set` (множество) — это гетерогенная не упорядоченная коллекция уникальных объектов. К ней применимы операции из теории множеств, такие как пересечение, объединение, разность.
- `set` создается с помощью конструктора `set()` либо литерала `{}`. Но `{}` подходит только для инициализации не пустого множества, а использование пустых скобок приведет к созданию словаря.
- Тип `frozenset` — это неизменяемое множество.
- `frozenset` создается с помощью конструктора `frozenset()`.
- Для того чтобы объект мог выступать элементом в `set`, `frozenset`, он должен быть хешируемым.
- Типы `set` и `frozenset` реализованы на базе хеш-таблицы.
Наша группа в telegram. Здесь можно задавать вопросы и общаться.
Задонатить. Если вам нравится курс, вы можете поддержать развитие площадки!