Списки, словари и множества в Python: Множества

Списки, словари и множества в Python

2. Множества

Множество (set)

Множество в языке Python — это структура данных, эквивалентная множествам в математике. Элементы могут быть различных типов. Порядок элементов не определён.

Действия, которые можно выполнять с множеством:

добавлять и удалять элементы,
проверять принадлежность элемента множеству,
перебирать его элементы,
выполнять операции над множествами (объединение, пересечение, разность).

Операция “проверить принадлежность элемента” выполняется в множестве намного быстрее, чем в списке.

Элементами множества может быть любой неизменяемый тип данных: числа, строки, кортежи.

Изменяемые типы данных не могут быть элементами множества, в частности, нельзя сделать элементом множества список (вместо этого используйте неизменяемый кортеж) или другое множество. Требование неизменяемости элементов множества накладывается особенностями представления множества в памяти компьютера.

Задание множеств

Множество задается перечислением в фигурных скобках. Например:

A = {1, 2, 3}

Исключением явлеется пустое множество:

A = set()       # A -- множество
D = {}          # D -- не пустое множество, а пустой словарь!

Если функции set передать в качестве параметра список, строку или кортеж, то она вернет множество, составленное из элементов списка, строки, кортежа. Например:

>>> A = set('qwerty')
>>> print(A)
{'e', 'q', 'r', 't', 'w', 'y'}.

Каждый элемент может входить в множество только один раз.

>>> A = {1, 2, 3}
>>> B = {3, 2, 3, 1}
>>> print(A == B) # A и B — равные множества.
True
>>> set('Hello')
{'H', 'e', 'l', 'o'}

Работа с элементами множеств

Операция	Значение	Трудоемкость
`x in A`	принадлежит ли элемент `x` множеству `A` (возвращают значение типа `bool`)	O(1)
`x not in A`	то же, что `not x in A`	O(1)
`A.add(x)`	добавить элемент `x` в множество `A`	O(1)
`A.discard(x)`	удалить элемент `x` из множества `A`	O(1)
`A.remove(x)`	удалить элемент `x` из множества `A`	O(1)
`A.pop()`	удаляет из множества один случайный элемент и возвращает его	O(1)

Как мы видим, по времени стандартные оперцаии с одним элементом множества выполняются за O(1).

Поведение discard и remove различается тогда, когда удаляемый элемент отсутствует в множестве: discard не делает ничего, а метод remove генерирует исключение KeyError. Метод pop также генерирует исключение KeyError, если множество пусто.

При помощи цикла for можно перебрать все элементы множества:

Primes = {2, 3, 5, 7, 11}
for num im Primes:
    print(num)

Из множества можно сделать список при помощи функции list:

>>> A = {1, 2, 3, 4, 5}
>>> B = list(A)
[1, 2, 3, 4, 5]

Упражнение №2

Вывести на экран все элементы множества A, которых нет в множестве B.

A = set('bqlpzlkwehrlulsdhfliuywemrlkjhsdlfjhlzxcovt')
B = set('zmxcvnboaiyerjhbziuxdytvasenbriutsdvinjhgik')
for x in A:
    ...

Операции с множествами, обычные для математики

Операция	Значение	Трудоемкость

A \| B A.union(B)	Возвращает множество, являющееся объединением множеств `A` и `B`.	O(len(A)+len(B))
A \| = B A.update(B)	Записывает в A объединение множеств `A` и `B`.	O(len(A)+len(B))
A & B A.intersection(B)	Возвращает множество, являющееся пересечением множеств `A` и `B`.	O(min(len(A), len(B))
A &= B A.intersection_update(B)	Записывает в A пересечение множеств `A` и `B`.	O(min(len(A), len(B))
A - B A.difference(B)	Возвращает разность множеств `A` и `B` (элементы, входящие в A, но не входящие в B).	O(len(A)+len(B))
A -= B A.difference_update(B)	Записывает в A разность множеств `A` и `B`.	O(len(A)+len(B))
A ^ B A.symmetric_difference(B)	Возвращает симметрическую разность множеств `A` и `B` (элементы, входящие в A или в B, но не в оба из них одновременно).	O(len(A)+len(B))
A ^= B A.symmetric_difference_update(B)	Записывает в A симметрическую разность множеств `A` и `B`.	O(len(A)+len(B))
A <= B A.issubset(B)	Возвращает True, если A является подмножеством B.	O(len(A))
A >= B A.issuperset(B)	Возвращает True, если B является подмножеством A.	O(len(B))
A < B	Эквивалентно A <= B and A != B	O(len(A))
A > B	Эквивалентно A >= B and A != B	O(len(B))

В случае, если нужно провести процедуру, затрагивающую все элементы множества, то его трудоемкость будет O(N).