Множества

Множество (set) – неупорядоченный набор различных значений. Записывается фигурными скобками; каждый элемент встречается не больше одного раза.

Множество удобно получать из готовой последовательности: set([1, 2, 2, 3]) убирает повторы, set('мама') оставляет две разные буквы. Готовое литеральное множество – {1, 2, 3}.

Порядок элементов не гарантирован: множество хранит их так, как удобно ему, а не в порядке добавления. Два множества с одинаковыми элементами равны независимо от порядка.

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

a = {1, 2, 3}
print(a)             # {1, 2, 3}

print(set([1, 2, 2, 3]))   # {1, 2, 3} – повтор исчез
print(set('мама'))          # {'м', 'а'} – три буквы стали двумя

print(type({}))      # <class 'dict'> – это словарь
print(type(set()))   # <class 'set'> – вот пустое множество
print(len(set('мама')))   # 2 – различных букв
print({1, 2} == {2, 1})    # True – порядок не важен

Индексов у множества нет. Обращение s[0] даёт TypeError: элементы не упорядочены, и «нулевого» среди них не существует. Взять элемент по номеру можно только после превращения в список – и тогда порядок будет произвольным.

remove() и discard() различаются ровно отношением к отсутствию элемента: первый считает это ошибкой, второй – нормальным случаем.

a = {1, 2, 3}
a.add(4)          # {1, 2, 3, 4}
a.add(3)          # {1, 2, 3, 4} – тройка уже была
print(a)

a.discard(99)     # нет такого – и ладно
print(a)          # {1, 2, 3, 4}

print(a.pop())    # 1 (какой именно – не гарантировано)
print(a)          # {2, 3, 4}

a.remove(99)      # KeyError: 99

print(a[0])       # TypeError: 'set' object is not
                  # subscriptable
print(list(a)[0]) # 2 – но порядок произвольный

Главное применение множества – ответ на вопрос «есть ли такой элемент».

x in a работает и для списка, и для множества, но устроено по-разному. Список перебирает элементы по порядку: чтобы убедиться, что значения нет, он просматривает все. Множество хранит элементы так, что место нужного вычисляется сразу, без перебора, – поэтому и на тысяче элементов ответ приходит за одно действие.

На маленьких списках разница не видна. На больших – в десятки и сотни раз, и именно поэтому проверку «есть ли» на большом наборе делают через множество. Как это устроено внутри, разберём в уроке 12.2.

Пример: в кружок по шахматам ходят Аня, Борис и Вера, в кружок по программированию – Борис и Глеб.

Операторы: a | b – объединение, a & b – пересечение, a - b – разность, a ^ b – симметричная разность. У каждой операции есть и метод.

Разность несимметрична: a - b и b - a – разные множества. Остальные три от порядка не зависят. Оператор короче, метод привычнее тем, кто пришёл из других языков.

chess = {'Аня', 'Борис', 'Вера'}
code = {'Борис', 'Глеб'}

print(chess | code)   # {'Аня', 'Борис', 'Вера', 'Глеб'}
print(chess & code)   # {'Борис'}
print(chess - code)   # {'Аня', 'Вера'}
print(chess ^ code)   # {'Аня', 'Вера', 'Глеб'}
print(code - chess)   # {'Глеб'} – разность несимметрична

# порядок в выводе может отличаться – это нормально

Множество seen накапливает всё, что цикл уже прошёл. На каждом шаге проверка x in seen отвечает, встречался ли элемент раньше, – и после проверки элемент кладут в seen. Так находят первое повторённое число и вообще отвечают на вопрос «было ли уже такое».

Только неизменяемые значения: числа, строки, кортежи. Список положить нельзя – TypeError: unhashable type: 'list'.

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

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

a = {1, 2, 3}
print([1, 2] in a)   # TypeError: unhashable type: 'list'

b = {(0, 0), (0, 1)}
print((0, 1) in b)   # True – кортеж неизменяем

c = {'a', 'b'}
print('a' in c)      # True – строка тоже неизменяема

Порядок элементов множества не гарантирован, поэтому печатать его напрямую для читателя бессмысленно: от запуска к запуску порядок может отличаться. Результат выводят через sorted() – она возвращает список в понятном порядке.

И вторая короткая запись: len(set(a)) – число различных элементов в списке a. Часто именно это и спрашивается в задаче, а сам список разных значений не нужен.

a = [3, 1, 3, 2, 1]
print(len(set(a)))       # 3 – различных чисел
print(sorted(set(a)))    # [1, 2, 3] – и в понятном порядке
print(set(a))            # {1, 2, 3} – порядок не гарантирован