set - множества

Множества в языке Python позволяют хранить только уникальные объекты и во многом аналогичны математическим множествам. Допустим у нас есть строка 'ABCABCABCABCDABCABC', если передать данную строку функции set(), то она будет преобразована в множество:

>>> set('ABCABCABCABCDABCABC')
{'A', 'C', 'B', 'D'}

Как видите, в множество поали только уникальные символы. Причем, при быстром взгляде на эту строку, могло показаться, что она состоит только из символов'A', 'B' и 'C', но на самом деле в ней был спрятан еще один символ - 'D'. Именно поэтому множества очень удобно использовать для поиска уникальных значений, например, в списках:

>>> L = [1, 0, 1, 2, 0, 1, 0, 2, 3]
>>>
>>> set(L)
{0, 1, 2, 3}

Множества крайне удобны еще и тем что поддерживают ряд специфичных для множеств операций. Допустим у нас есть две строки:

>>> a = 'ACBBACBDEFAEAFBBA'
>>> b = 'DIIHFIDHFGDFGIEDF'

Что бы узнать, есть ли у данных строк общие символы, мы можем преобразовать их в множества:

>>> A = set(a)
>>> A
{'D', 'C', 'E', 'A', 'F', 'B'}
>>>
>>> B = set(b)
>>> B
{'D', 'I', 'E', 'H', 'F', 'G'}

А затем выполнить следующую операцию:

>>> A & B
{'D', 'E', 'F'}

Еще мы можем посмотреть какие буквы есть в A но не содержатся в B:

>>> A - B
{'A', 'C', 'B'}

Или взглянуть только на те символы, которые не являются общими для двух множеств:

>>> A ^ B
{'A', 'C', 'G', 'I', 'B', 'H'}

Поскольку A и B являются множествами, то изобразить эти операции можно с помощью привычных диаграмм Вена:

Фрагмент социального графа для демонстрации работы с типом данных dict Python


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

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

>>> a = {1, 2, 3, 4}
>>> a
{1, 2, 3, 4}
>>>
>>> b = {1}     # множество с одним элементом, равносильно b = {1,}
>>> b
{1}

А вот создать пустое множество с помощью {} уже не получится, так как пустые фигурные скобки являются литералом словарей:

>>> c = {}
>>> type(c)
<class 'dict'>

Создать пустое множество можно только с помощью функции set():

>>> d = set()
>>> d
set()

Если передать функции set() некоторый объект, то она попытается преобразовать его в множество:

>>> # множество из элементов строки:
>>> set('abcabc')
{'b', 'a', 'c'}
>>>
>>>
>>> # множество из элементов списка:
>>> set([1, 2, 1, 2])
{1, 2}
>>>
>>>
>>> # множество из итератора range:
>>> set(range(4))
{0, 1, 2, 3}
>>>
>>>
>>> # множество из ключей словаря:
>>> set({'a': 1, 'b': 2, 'c': 3})
{'b', 'a', 'c'}

Если передать функции set() другое множество, то он будет возвращено как бы без изменений, но на самом деле будет возвращена его поверхностная копия:

>>> set({1, 2, 3})
{1, 2, 3}

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

>>> a = {1, 2, 3, 4}
>>> b = a        # 'a' и 'b' ссылаются на одно множество
>>>
>>> a.add(5)     #  поэтому изменения в 'a'
>>> a
{1, 2, 3, 4, 5}
>>>
>>> b            # влияют на 'b'
{1, 2, 3, 4, 5}

Поверхностное копирование множеств позволяет избежать таких проблем:

>>> b = set(a)
>>>
>>> a.add(6)
>>> a
{1, 2, 3, 4, 5, 6}
>>>
>>> b
{1, 2, 3, 4, 5}

Множества могут быть созданы с помощью генераторов множеств:

>>> {i for i in 'abccbaabc'}
{'b', 'a', 'c'}

Элементы множеств

Элементами множеств могут быть только неизменяемые объекты таких типов как int, float, complex, str, frozenset, а чаще всего и объекты типа tuple

>>> # множество из чисел типа int:
>>> set([1, 2, 3])
{1, 2, 3}
>>> 
>>> # множество из чисел типа float:
>>> set([.1, .2, .3])
{0.2, 0.1, 0.3}
>>> 
>>> # множество из чисел типа complex:
>>> set([1+1j, 2+2j, 3+3j])
{(2+2j), (3+3j), (1+1j)}
>>>
>>> # множество из строк:
>>> set(['aa', 'bb', 'aa'])
{'aa', 'bb'}
>>>
>>> # множество из неизменяемых множеств frozenset:
>>> set([frozenset([1, 2, 3]), frozenset(['a', 'b', 'c'])])
{frozenset({1, 2, 3}), frozenset({'b', 'a', 'c'})}

Но если попытаться создать множества из элементов изменяемого типа (list, set, dict), то это приведет к ошибке:

>>> # создать множество списков не получится:
>>> set([[1, 2], [3, 4], [5, 6]])
TypeError: unhashable type: 'list'
>>>
>>>
>>> # так же как и множество множеств:
>>> set([{1, 2, 3}, {'a', 'b', 'c'}])
TypeError: unhashable type: 'set'
>>>
>>>
>>> # так же не выйдет множество и из словарей:
>>> set([{'a': 1, 'b': 2}, {'c': 3, 'd': 4}])
TypeError: unhashable type: 'dict'

Объекты типа tuple могут быть элементами множеств, только если они сами состоят из неизменяемых объектов:

>>> a = set([(1, 2), (2, 2), (2, 1), (1, 2)])
>>> a
{(1, 2), (2, 2), (2, 1)}

Это связано с тем, что на самом деле объектами множеств могут быть не просто неизменяемые объекты, они должны быть еще и хешируемыми. Хешируемые объекты имеют специальный метод __hash__() возвращаемое значение которого, у таких элементов не меняется с момента создания и до момента утилизации.

В том случае если кортеж состоит из неизменяемых элементов, то он является хешируемым (и неизменяемым):

>>> a = (1, 2, 3)    # состоит из неизменяемых элементов
>>> 
>>> a.__hash__()    # значит обладает хешем
-2022708474
>>>
>>> a[1] = 222     # значит и сам не может быть изменен:
TypeError: 'tuple' object does not support item assignment

Но если в кортеже есть изменяемые элементы, то эти элементы могут быть изменены:

>>> b = (1, [2, 3])
>>>
>>> b[0] = 111    # изменить не получится
TypeError: 'tuple' object does not support item assignment
>>>
>>>
>>> b[1][0] = 222    # а вот это сработает
>>> b
(1, [222, 3])

Поэтому и хеш для таких кортежей не создается:

>>> b.__hash__()
TypeError: unhashable type: 'list'

Но если ваши кортежи состоят из неизменяемых объектов, то можете смело создавать из них множество.


Обход множеств в цикле

Множества так же как последовательности (строки, списки и т.д) и отображения (словари) являются коллекциями, т.е. могут хранить сложные структуры данных (например, кортежи). Но так как элементы множеств не снабжены никакими идентификаторами (ни индексами, ни ключами), то множества не поддерживают операторы извлечения среза [START:STOP:STEP] и извлечения элемента по ключу []. Тем не менее множества поддерживают оператор проверки на вхождение in (а так же not in) и функцию определения размера len():

>>> a = {1, 2, 3, 4}
>>>
>>> len(a)
4
>>>
>>> 1 in a
True
>>>
>>> 5 not in a
True

Множества поддерживают механизм итерирования и их элементы могут быть получены перебором в цикле for... in...:

>>> s = set('nvdfkjvndfkkssdskcdjnjsc')
>>>
>>> for i in s:
...     print(i.upper())
...
J
N
C
K
F
S
D
V

Чаще всего множества используются для итерирования уникальных элементов последовательностей. И тут возможны два случая. Давайте рассмотрим следующий список:

>>> l = list('vvscscadaceer')
>>> l
['v', 'v', 's', 'c', 's', 'c', 'a', 'd', 'a', 'c', 'e', 'e', 'r']

В первом случае, может быть неважно в каком порядке обрабатываются элементы, главное обрабатывать только уникальные:

>>> for i in set(l):
...     print(i*7)
...
ccccccc
eeeeeee
aaaaaaa
rrrrrrr
sssssss
ddddddd
vvvvvvv

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

>>> s = set()
>>>
>>> for i in l:
...     if i not in s:
...         s.add(i)
...         print(i*l.index(i))
...

ss
ccc
aaaaaa
ddddddd
eeeeeeeeee
rrrrrrrrrrrr

Так же множества могут выступать в роли итерируемого объекта в любых генераторах:

>>> [i.upper() for i in set(l)]
['C', 'E', 'A', 'R', 'S', 'D', 'V']

frozenset - неизменяемые множества

Множества типа frozenset в отличие от set являются неизменяемыми и хешируемыми, т.е. могут быть ключами словарей и могут быть подмножествами других множеств. Создать фиксированное множество можно только с помощью функции frozenset(), без аргументов данная функция создает пустое фиксированное множество:

>>> a = frozenset()
>>> a
frozenset()

Если frozenset() передать итерируемый объект, то будет выполнена попытка преобразовать его в фиксированное множество:

>>> b = frozenset('abababcdcdcd')
>>> b
frozenset({'b', 'a', 'd', 'c'})

Ну а если передать frozenset() другое множество, то будет возвращена его поверхностная копия:

>>> c = frozenset({'a', 'b', 'c', 'd'})
>>> c
frozenset({'b', 'a', 'd', 'c'})

Фиксированные множества действительно могут быть ключами словарей и подмножествами других множеств, что может быть удобно в некоторых ситуациях:

>>> a = frozenset('abc')
>>> b = frozenset('ijk')
>>> c = frozenset('xyz')
>>>
>>>
>>> # 'a', 'b' и 'c' могут быть ключамми словаря:
>>> set_key = {a: 1, b: 2, c: 3}
>>> set_key
{frozenset({'b', 'a', 'c'}): 1, frozenset({'k', 'j', 'i'}): 2, frozenset({'y', 'z', 'x'}): 3}
>>>
>>>
>>> # 'a', 'b' и 'c' могут быть подмножествами:
>>> set_of_sets = {a, b, c}
>>> set_of_sets
{frozenset({'b', 'a', 'c'}), frozenset({'y', 'z', 'x'}), frozenset({'k', 'j', 'i'})}

Фиксированные множества поддерживают только те операторы и методы которые не приводят к изменению объектов, но это не мешает делать ссылки переменных на резульат манипуляций над фиксированными множествами, например:

>>> a = frozenset('abc')
>>>
>>> a |= {'d'}
>>>
>>> a
frozenset({'b', 'a', 'd', 'c'})

В этом смысле, множества похожи на строки или кортежи, которые тоже являются неизменяемыми, но которые могут служить "основой" для создания новых неизменяемых объектов.

Двухместные операторы множеств, могут быть применены к множествам типа set и frozenset одновременнно, но тип результата, будет зависеть от того, какой тип указан первым в этом операторе:

>>> a = set('abcdef')
>>> b = frozenset('defghi')
>>>
>>> a & b
{'f', 'd', 'e'}
>>>
>>> b & a
frozenset({'f', 'd', 'e'})

При этом множества и фиксированные множества могут проверяться на равенство состава элементов:

>>> a == b
False
>>>
>>> a & b == b & a
True

Поверхностное и глубокое копирование

Если несколько переменных ссылается на одно и то же множество, например вот так:

>>> x = set('abc')
>>> x
{'b', 'a', 'c'}
>>>
>>> y = x      # x и y ссылаются на одно и тоже множество
>>> y
{'b', 'a', 'c'}

То изменение данных посредством одной из них, повлияет на все остальные переменные:

>>> x.add('d')     # изменения в x
>>> x
{'b', 'a', 'd', 'c'}
>>>
>>> y     # повлияли на y
{'b', 'a', 'd', 'c'}
>>> x = frozenset('abc')
>>> x
frozenset({'b', 'a', 'c'})
>>>
>>> y = x
>>> y
frozenset({'b', 'a', 'c'})
>>>
>>>

Что бы избежать подобного поведения необходимо создать поверхностную копию множества, передав его функции set() или вызвав метод .copy():

>>> x = set('abc')
>>>
>>> y = set(x)
>>> z = x.copy()
>>>
>>> x.add('d')
>>> x
{'b', 'a', 'd', 'c'}
>>>
>>> y
{'b', 'a', 'c'}
>>>
>>> z
{'b', 'a', 'c'}

Поскольку, множества могут хранить только хешируемые объекты (т.е. те которые точно не могут быть изменены), то проблем с глубоким копированием возникнуть не должно. Однако, чисто теоретически, кто-то может создать объекты, метод __hash__() которых переопределен по другому (если честно, даже не могу представить кому и зачем это может понадобиться). То в этом случае, в множестве могут оказаться нехешируемые (!) и даже одинаковые элементы. В этом случае, придется прибегать к глубокому копированию множеств с помощью функции deepcopy() из модуля copy() стандартной библиотеки.