# Глава 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` реализованы на базе хеш-таблицы.