Метка: множество

«Сломанный» set

Вопрос: может ли set содержать два одинаковых объекта?

Ответ: да, запросто!

Делаем класс:

class Foo:
    def __init__(self, x):
        self.x = x
    def __hash__(self):
        return self.x
    def __eq__(self, other):
        return self.x == other.x
    def __repr__(self):
        return f'Foo({self.x})'

# создаем set из трех разных объектов
hacker = Foo(20)
s = {Foo(10), hacker, Foo(30)}

print(s)  # {Foo(10), Foo(20), Foo(30)}

hacker.x = 30  # взлом системы
print(s)  # {Foo(10), Foo(30), Foo(30)}

from collections import Counter
c = Counter(s)
print(c)  # Counter({Foo(30): 2, Foo(10): 1})

Как это? set запоминает хэш объекта при вставке, а потом не следит за тем, меняется ли как-то объект или нет, это было бы очень накладно. Изначально мы вставляли 20, но потом уже поменяли его на 30, тем самым сломав set.

«Починить» такой set можно, сделав из него список, а потом новый set, тогда хэши будут заново пересчитаны. Лучше до такого не доводить!

s2 = set(list(s))
print(s2)  # {Foo(10), Foo(30)}

Примечание: а метод s.copy() не сработает, потому что он копирует уже вычисленные хэши.

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

Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈

Множества в Python

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

О неизменяемых множествах написано в конце этой статьи.

CPython: внутри множества реализованы как хэш-таблицы, в которых есть только ключи без значений и добавлены некоторые оптимизации, которые используют отсутствие значений. Проверка членства выполняется за время O(1), так как поиск элементов в хэш-таблицы тоже выполняется за О(1). Если интересно, как это реализовано на С: вот ссылка.

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

Сформировать множество можно несколькими способами. Самый простой – перечислить элементы через запятую внутри фигурных скобок {}. Множество может содержать элементы разных типов, главное, чтобы они были неизменяемы. Поэтому кортеж можно поместить в множество, а список – нельзя.

>>> my_set = {1, 2, 3, 4}

>>> my_hetero_set = {"abc", 3.14, (10, 20)}  # можно с кортежем

>>> my_invalid_set = {"abc", 3.14, [10, 20]}  # нельзя со списком
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

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

>>> my_set2 = set([11, 22, 33])
>>> my_set2
{33, 11, 22}

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

>>> my_set4 = set({"a": 10, "b": 20})
>>> my_set4
{'b', 'a'}

>>> my_set5 = set("hello")
>>> my_set5
{'h', 'l', 'e', 'o'}

Как создать пустое множество? {} – вернет нам пустой словарик, а не множество. Поэтому, нужно использовать set() без аргументов.

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

>>> this_is_a_set = set()
>>> type(this_is_a_set)
<class 'set'>

Изменение множеств

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

Добавление одного элемента выполняется методом add(). Нескольких элементов из коллекции или нескольких коллекций – методом update():

>>> my_set = {44, 55}
>>> my_set.add(50)
>>> my_set
{50, 44, 55}

>>> my_set.update([1, 2, 3])
>>> my_set
{1, 2, 3, 44, 50, 55}

>>> my_set.update([2, 3, 6], {1, 50, 60}) 
>>> my_set
{1, 2, 3, 6, 44, 50, 55, 60}

>>> my_set.update("string")
>>> my_set
{1, 2, 3, 6, 'i', 44, 'r', 50, 's', 55, 'n', 'g', 60, 't'}

Естественно, что при добавлении элементов дубликаты игнорируются.

Удаление элементов из множества

Для удаления элемента существуют методы discard() и remove(). Делают они одно и тоже, но если удаляемого элемента нет во множестве, то discard() оставит множество неизменным молча, а remove() – бросит исключение:

>>> my_set = {1, 2, 3, 4, 5, 6}
>>> my_set.discard(2)
>>> my_set
{1, 3, 4, 5, 6}

>>> my_set.remove(4)
>>> my_set
{1, 3, 5, 6}

>>> my_set.discard(10)
>>> my_set
{1, 3, 5, 6}

>>> my_set.remove(10)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 10

Также есть метод pop(), который берет какой-нибудь (первый попавшийся) элемент множества, удаляет его и возвращает как результат:

>>> my_set = {3, 4, 5, 6, 1, 2}
>>> my_set
{1, 2, 3, 4, 5, 6}
>>> my_set.pop()
1
>>> my_set
{2, 3, 4, 5, 6}

Наконец, очистить множество (т.е. удалить все его элементы) можно методом clear(): 

>>> my_set = {1, 2, 3}
>>> my_set.clear()
>>> my_set
set()

Проверка членства

Узнать есть ли элемент в множестве очень легко оператором in (или not in, если хотим убедиться в отсутствии элемента):

>>> s = {"banana", "apple"}
>>> "banana" in s
True
>>> "tomato" not in s
True

Таким образом проверяется членства одного элемента, если нужно узнать является ли одно множество подмножеством другого, то оператор in тут не подойдет:

>>> {1, 2} in {1, 2, 3}
False

Тут подойдут операторы < и >. Чтобы получить True, с «широкой» стороны оператора должно стоять множество, полностью содержащее множество, стоящее по «узкую» сторону галочки:

>>> {1, 2} < {1, 2, 3, 4}
True
>>> {5, 6, 7, 8} > {5, 8}
True
>>> {1, 2, 3} < {1, 2, 4}
False

Итерация множеств

Пробежаться по элементам множества также легко, как и по элементам других коллекций оператором for-in (порядок обхода не определен точно):

my_set = {"Moscow", "Paris", "London"}
for elem in my_set:
    print(elem)
Moscow
London
Paris

Операции над множествами

Самое интересное – проводить математические операции над множествами.

Рассмотрим два множества A и B:

A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7, 8}

Объединение

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

В Python используется либо метод union(), либо оператор вертикальная черта «|»:

>>> A = {1, 2, 3, 4, 5}
>>> B = {4, 5, 6, 7, 8}

>>> A | B
{1, 2, 3, 4, 5, 6, 7, 8}

>>> A.union(B)
{1, 2, 3, 4, 5, 6, 7, 8}

>>> B.union(A)
{1, 2, 3, 4, 5, 6, 7, 8}

Пересечение множеств

Пересечение множеств – множество, в которое входят только общие элементы, то есть которые есть и в первом, и во втором множестве. Также коммуникативная операция.

Пересечение вычисляют методом intersection() или оператором амперсандом «&»:

>>> A = {1, 2, 3, 4, 5}
>>> B = {4, 5, 6, 7, 8}

>>> A & B
{4, 5}

>>> B & A
{4, 5}

>>> A.intersection(B)
{4, 5}

Разность множеств

Разность множеств A и В – множество элементов из A, которых нет в B. Не коммуникативная операция!

Выполняется знаком минус «-» или оператором difference():

>>> A = {1, 2, 3, 4, 5}
>>> B = {4, 5, 6, 7, 8}

>>> A - B
{1, 2, 3}

>>> B - A
{8, 6, 7}

>>> A.difference(B)
{1, 2, 3}

>>> B.difference(A)
{8, 6, 7}

Как видно есть разница, в каком порядке идут операнды.

Симметричная разность

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

Используется метод symmetric_difference() или оператор крышка «^»:

>>> A = {1, 2, 3, 4, 5}
>>> B = {4, 5, 6, 7, 8}

>>> A ^ B
{1, 2, 3, 6, 7, 8}

>>> B ^ A
{1, 2, 3, 6, 7, 8}

>>> A.symmetric_difference(B)
{1, 2, 3, 6, 7, 8}

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

>>> A ^ B == (A - B) | (B - A)   # объединение простых разностей
True

>>> A ^ B == (A | B) - (A & B)   # разность объединения и пересечения
True

Прочее

Ко множествам можно применять стандартные функции all(), any(), enumerate(), len(), max(), min(), sorted(), sum(). Описания их ищите тут.

Прочие методы класса set:

copy() Возвращает копию множества
difference_update(other_set)Удаляет из этого множества все элементы, которые есть во множестве, переданным в аргументе
intersection_update(other_set)Обновляет это множество элементами из пересечения множеств
isdisjoint(other_set)Возвращает True, если множества не пересекаются
issubset(other_set)Возвращает True, если это множество является подмножеством другого
issuperset(other_set)Возвращает True, если это множество является надмножеством другого
symmetric_difference_update(other_set)Добавляет в это множество симметричную разность этого и другого множеств

Замороженное множество

Замороженное множество (frozen set) также является встроенной коллекцией в Python. Обладая характеристиками обычного множества, замороженное множество не может быть изменено после создания (подобно тому, как кортеж является неизменяемой версией списка).

Будучи изменяемыми, обычные множества являются нехешируемыми (unhashable type), а значит не могут применятся как ключи словаря или элементы других множеств.

Замороженные множества являются хэшируемыми, а значит могут быть ключами словаря и элементами других множеств.

Создаются замороженные множества функцией frozenset(), где аргументом будет другая коллекция. Примеры:

>>> A = frozenset({1, 2, 3})
>>> A
frozenset({1, 2, 3})

>>> B = frozenset(['a', 'b', 'cd'])
>>> B
frozenset({'cd', 'b', 'a'})

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

>>> A = frozenset('hello')
>>> B = frozenset('world')
>>> A | B
frozenset({'o', 'r', 'd', 'e', 'l', 'h', 'w'})
>>> A & B
frozenset({'o', 'l'})
>>> A ^ B
frozenset({'d', 'e', 'h', 'r', 'w'})

Теперь вы знаете много о множествах в Python.

Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈