Множество set и frozenset в Python

Изменяемое/НЕизменяемое множество set/frozenset

Множество - это неупорядоченный набор различных хешированных hashable объектов. Обычно множества используются в тестировании вхождения элемента, удаление дубликатов из последовательности и вычисление математических операций, таких как пересечение, объединение, разность и т. д.

Как и другие коллекции, множества поддерживают операции x in set, len(set) и for x in set. Будучи неупорядоченной коллекцией, множества не записывают положение элемента или порядок вставки. Соответственно, не поддерживают индексацию, нарезку или другое поведение, подобное упорядоченной последовательности.

В настоящее время существует два встроенных типа множеств: set и frozenset:

• Тип set является ИЗМЕНЯЕМЫМ множеством, содержимое может быть изменено с помощью таких методов, как set.add() и set.remove(), также поддерживает операции доступные frozenset. Поскольку тип set является изменяемым, он не имеет хеш-значения и не может использоваться ни как ключ словаря, ни как элемент другого множества.
• Тип frozenset является НЕизменяемым и хешируемым множеством, его содержимое не может быть изменено после его создания, поэтому он может использоваться как ключ словаря или как элемент другого множества. Дополнительно смотрите операции доступные frozenset

Свойства множеств set и frozenset:

• Множества не поддерживают сортировку. (Если необходимо отсортировать множество, то посмотрите в сторону стороннего модуля sortedcontainers, вам понравится.)
• Множества не поддерживают индексирование элементов.
• Двоичные операции, которые смешивают типы set с frozenset, возвращают тип первого операнда. Например: frozenset('ab') | set('bc') возвращает тип frozenset.

• Оба типа set и frozenset поддерживают операции сравнения. Тип set сравниваются с типом frozenset на основе их членов. Например:

  set('abc') == frozenset('abc')
  # True
  
  set('abc') in set([frozenset('abc')])
  # True
  

• Два множества равны тогда и только тогда, когда каждый элемент каждого множества содержится в другом. Каждый является подмножеством другого.

• Одно множество меньше другого тогда и только тогда, когда первое множество является правильным подмножеством второго множества. Является подмножеством, но не равно.

• Одно множество больше другого множества тогда и только тогда, когда первое множество является собственным надсетом второго множества. Является надсетом, но не равно.

• Любые два непустых непересекающихся множества не равны и не являются подмножествами друг друга, поэтому все следующие возвращают False: a<b, a==b или a>b.

В языке программирования Python множества представлены классом set() и frozenset().

Создание множеств set и frozenset:

• С помощью класса set() можно создавать как пустые изменяемые множества так и выполнять преобразования последовательностей хешируемых объектов в изменяемые множества.
• С помощью класса frozenset() можно создавать как пустые неизменяемые множества так и выполнять преобразования последовательностей хешируемых объектов в неизменяемые множества.
• При выполнении преобразования с помощью классов set() и frozenset() удаляются дубликаты элементов последовательности.
• Непустые множества set (не frozenset) можно еще создать, поместив разделенную запятыми последовательность в фигурные скобки, например: s = {'jack', 'sjoerd'}.

Дополнительно смотрите использование множеств set в Python.

Примеры создания set() и frozenset(), некоторые операции с изменяемыми множествами:

# Чтобы создать пустое множество необходимо 
# использовать `set()`, а не `{}`, т.к. пустые фигурные 
# скобки создадут пустой [словарь][t-dict].
# Создание пустых множеств
>>> set()
# set()

>>> frozenset()
# frozenset()

# Создание непустых изменяемых множеств
>>> s = {'a', 'b', 'c', 'd'}
>>> s
# {'a', 'b', 'c', 'd'}

# При преобразовании последовательности в 
# множество удаляются дубликаты элементов
line = 'abracadabra'
>>> a = set(line)
>>> a
# {'a', 'r', 'd', 'c', 'b'}

lst = ['a', 'b', 'c', 'd', 'a', 'b', 'c', 'd']
>>> b = set(lst)
>>> b
# {'a', 'b', 'c', 'd'}

# Добавление элемента к изменяемому множеству
>>> a.add(10)
# {'a', 10, 'r', 'd', 'c', 'b'}

# Удаление элемента из изменяемого множества
# происходит по его значению
>>> a.remove('r')
>>> a
# {'a', 10, 'd', 'c', 'b'}

# Метод `.pop()` извлекает и удаляет случайный элемент
# изменяемого множества
>>> a.pop()
# 'a'

# НЕИЗМЕНЯЕМОЕ МНОЖЕСТВО
>>> lst = [0, 1, 2, 3, 4, 0, 1, 2, 3, 4]
>>> s = frozenset(lst)
>>> s
# frozenset({0, 1, 2, 3, 4})

# пробуем удалить элемент
>>> s.remove(1)
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# AttributeError: 'frozenset' object has no attribute 'remove'

Сортировка множества set

Для сортировки множества set необходимо установить сторонний модуль pip install sortedcontainers (желательно в виртуальное окружение)

>>> from sortedcontainers import SortedSet
>>> ss = SortedSet('abracadabra')
>>> ss
# SortedSet(['a', 'b', 'c', 'd', 'r'])
>>> ss.bisect_left('c')
# 2

Эта операция выполняются быстрее линейного времени и потребляет на 66% меньше накладных расходов.