Множества
Множество
set — коллекция уникальных элементов без порядка. Как и ключи словаря, элементы должны быть хешируемыми.
colors = {"red", "green", "blue", "red"}
print(colors, len(colors)) # дубликат исчез; порядок не гарантирован
unique = set([3, 1, 3, 2, 1])
print(unique)
letters = set("hello")
print(letters)
empty = set() # {} — это пустой СЛОВАРЬ
print(type({}), type(empty))
Добавление и удаление
s = {1, 2}
s.add(3)
s.update([4, 5]) # добавить несколько
s.discard(100) # удалить, если есть — без ошибки
s.remove(1) # удалить; KeyError, если нет
x = s.pop() # удалить и вернуть произвольный элемент
print(s, x)
Быстрая проверка принадлежности
import time
items_list = list(range(1_000_000))
items_set = set(items_list)
t = time.perf_counter()
for _ in range(20):
999_999 in items_list
print(f"список: {time.perf_counter() - t:.4f} c")
t = time.perf_counter()
for _ in range(20):
999_999 in items_set
print(f"множество: {time.perf_counter() - t:.6f} c")
Классическая оптимизация
Если в цикле много раз проверяется x in collection — превратите коллекцию в множество один раз до цикла. O(n·m) становится O(n + m).
Операции над множествами
a = {1, 2, 3, 4}
b = {3, 4, 5}
print("объединение ", a | b, a.union(b))
print("пересечение ", a & b, a.intersection(b))
print("разность ", a - b, a.difference(b))
print("симм. разность", a ^ b, a.symmetric_difference(b))
print({1, 2} <= a, a >= {1, 2}, {1, 2} < a, a.isdisjoint({10, 20}))
Методы (union, intersection…) принимают любые итерируемые, а операторы требуют множества: a | [5] — ошибка, a.union([5]) — работает. Есть версии «на месте»: |=, &=, -=, ^=.
frozenset
Неизменяемое множество. Хешируется — значит, может быть ключом словаря или элементом другого множества.
fs = frozenset({1, 2})
groups = {fs: "пара", frozenset(): "пусто"}
print(groups[frozenset({2, 1})]) # порядок не важен
Типичные задачи
emails_sent = ["a@x.ru", "b@x.ru", "c@x.ru"]
emails_opened = ["b@x.ru", "c@x.ru", "c@x.ru"]
print("не открыли:", set(emails_sent) - set(emails_opened))
words = "to be or not to be".split()
print("уникальных слов:", len(set(words)))
# уникальные с сохранением порядка — через dict, а не set
print(list(dict.fromkeys(words)))
# анаграммы: одинаковые наборы букв? (для учёта количества — Counter или sorted)
print(set("listen") == set("silent"))
Порядок элементов
Не полагайтесь на порядок элементов в set при выводе. Если нужен порядок — sorted(s).
Итог
set— уникальные хешируемые элементы без порядка; пустое —set(), не{}.add,update,remove(с ошибкой),discard(без ошибки).x in s— O(1) в среднем.|&-^,<=(подмножество);frozenset— неизменяемый и хешируемый.
Практика решено 0 из 5
Какой тип у x = {}?
a = {1, 2, 3, 4}, b = {3, 4, 5}. Что получится?
| {3, 4} | {1, 2, 3, 4, 5} | {1, 2} | {1, 2, 5} | |
|---|---|---|---|---|
a & b |
||||
a | b |
||||
a - b |
||||
a ^ b |
Напишите функцию common_friends(a, b), которая по двум спискам друзей возвращает
отсортированный список общих друзей (без повторов).
Какие тесты проверяют код (3)
assert common_friends(["Аня", "Боря", "Вика"], ["Вика", "Гоша", "Аня"]) == ["Аня", "Вика"] assert common_friends(["x", "x"], ["x"]) == ["x"] assert common_friends([], ["a"]) == []
def common_friends(a, b):
return sorted(set(a) & set(b))
Напишите функцию has_duplicates(items), которая за O(n) проверяет, есть ли в списке повторяющиеся элементы.
Какие тесты проверяют код (3)
assert has_duplicates([1, 2, 3, 1]) is True assert has_duplicates([1, 2, 3]) is False assert has_duplicates([]) is False
def has_duplicates(items):
return len(set(items)) != len(items)
Почему x in some_set обычно быстрее, чем x in some_list?
Войдите, чтобы отмечать пройденные уроки.