Наборы

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

1. Автоматическая дедупликация: добавление одного и того же элемента дважды не имеет никакого эффекта.
2. Тест на членство O(1): x in s выполняется очень быстро даже с миллионами элементов (он основан на хеше, как и dicts).
3. Операции над множествами: объединение, пересечение, разность, симметричная разность.

Создание набора

vuoto = set()           # ATTENZIONE: {} è un dict vuoto, non un set!
numeri = {1, 2, 3}
da_lista = set([1, 1, 2, 3, 3, 3])   # {1, 2, 3}

Одни только фигурные скобки {} создают пустой словарь, а не набор: для пустого набора вам нужен set().

Изменение набора

s = {1, 2, 3}
s.add(4)         # {1, 2, 3, 4}
s.add(1)         # nessun effetto (già presente)
s.discard(99)    # rimuove se presente, silenzioso altrimenti
s.remove(2)      # rimuove o solleva KeyError

Установить операции

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

a | b    # {1, 2, 3, 4, 5, 6}     unione
a & b    # {3, 4}                  intersezione
a - b    # {1, 2}                  differenza (in a ma non in b)
a ^ b    # {1, 2, 5, 6}            differenza simmetrica (xor)

Существуют также формы методов (a.union(b), a.intersection(b), …), которые в Кроме того, принимаются любые итерации, а не только множества.

Тест на членство

parole = {"ciao", "mondo", "python"}
"ciao" in parole       # True   O(1)
"java" not in parole   # True

Для сравнения: поиск с помощью in внутри list равен O(n) и длится долго. списки это намного медленнее.

Замороженный набор: неизменяемая версия

frozenset({1, 2, 3}) — это хешируемая версия: это может быть ключ dict или элемент другого множества.

Настройка операций и производительности

Наборы реализованы в виде хеш-таблиц, что делает проверку членства (x in my_set) чрезвычайно быстрой: она выполняется за постоянное время O(1), в отличие от списков, где поиск занимает линейное время O(n). Кроме того, они поддерживают алгебраические операции, такие как объединение (|), пересечение (&) и разность (-).

Попробуйте это

Обзор упражнения

Дополнительная задача