На этом шаге мы приведем краткие сведения о множествах.
Начиная с этого шага, вы увидите, как в Python реализуются такие структуры данных, как изменяемое и неизменяемое множество и мультимножество (или тип bag, то есть мешок), с использованием встроенных типов данных и классов стандартной библиотеки. Однако сначала давайте составим краткое резюме по поводу того, что такое множество.
Множество представляет собой неупорядоченную коллекцию объектов, которая не допускает повторяющихся элементов. Как правило, множества используются для быстрой проверки принадлежности значения множеству, вставки новых значений в множество, удаления значений из множества и вычисления на множествах операций, таких как объединение или пересечение двух множеств.
Предполагается, что в "надлежащей" реализации множества операции проверки на принадлежность будут выполняться за быстрое O(1) время. Операции объединения, пересечения, разности и взятия подмножеств должны в среднем занимать O(n) времени. В реализациях множества, включенных в стандартную библиотеку Python, данные характеристики производительности соблюдаются.
См. https://wiki.python.org/moin/TimeComplexity.
Точно так же, как и словари, множества в Python обрабатываются особым образом и имеют свой синтаксический сахар, упрощающий их создание. Например, синтаксис выражения с фигурными скобками для множеств и конструкция включения в множество позволяют удобно определять новые экземпляры множеств:
vowels = {'a', 'e', 'i', 'o', 'u'}
squares = {x * x for x in range(10)}
Тем не менее следует быть осторожными: для того чтобы создать пустое множество, вам нужно вызвать конструктор set(). Использование фигурных скобок {} неоднозначно и вместо этого создаст пустой словарь.
Python и его стандартная библиотека предоставляют несколько реализаций множества. Давайте их рассмотрим.
На следующем шаге мы рассмотрим класс set.
