Зачем нужны множества?

Назначение множеств (sets) в Python

Множества (set) — это неупорядоченные коллекции уникальных элементов. Они решают специфические задачи более эффективно, чем списки или словари.

Основная проблема, которую решают множества

Задача: определить уникальные элементы

# Проблема 1: проверка уникальности медленная с list
items = ["apple", "banana", "apple", "cherry", "banana", "apple"]

# Медленно: O(n) для каждой проверки
def is_unique_slow(items):
    seen = []
    for item in items:
        if item in seen:  # Ищет в списке, O(n)
            return False
        seen.append(item)
    return True

# Быстро: O(1) для каждой проверки
def is_unique_fast(items):
    seen = set()
    for item in items:
        if item in seen:  # Ищет в set, O(1)
            return False
        seen.add(item)
    return True

print(is_unique_fast(items))  # False (есть дубликаты)

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

1. Создание и добавление

# Создание множества
colors = {"red", "green", "blue"}

# Создание из списка (удалит дубликаты)
numbers = list(range(10))
unique_numbers = set(numbers)  # {0, 1, 2, ..., 9}

# Добавление элемента
colors.add("yellow")
print(colors)  # {'red', 'green', 'blue', 'yellow'}

# Добавление дубликата (не добавляется)
colors.add("red")
print(colors)  # {'red', 'green', 'blue', 'yellow'} — no change

# Удаление элемента
colors.remove("red")  # ValueError если нет
colors.discard("red")  # Не выбросит ошибку если нет

2. Проверка принадлежности (O(1))

# Очень быстро!
colors = {"red", "green", "blue"}

if "red" in colors:  # O(1)
    print("Red is in colors")

if "yellow" not in colors:  # O(1)
    print("Yellow is not in colors")

# Сравните с list (O(n)):
color_list = ["red", "green", "blue"]
if "red" in color_list:  # O(n) — ищет в каждом элементе
    print("Red is in colors")

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

# Объединение (union) — все элементы из обоих
set_a = {1, 2, 3}
set_b = {3, 4, 5}
union = set_a | set_b  # или set_a.union(set_b)
print(union)  # {1, 2, 3, 4, 5}

# Пересечение (intersection) — общие элементы
intersection = set_a & set_b  # или set_a.intersection(set_b)
print(intersection)  # {3}

# Разница (difference) — элементы в A, но не в B
difference = set_a - set_b  # или set_a.difference(set_b)
print(difference)  # {1, 2}

# Симметричная разница (symmetric difference) — либо A, либо B, но не оба
sym_diff = set_a ^ set_b  # или set_a.symmetric_difference(set_b)
print(sym_diff)  # {1, 2, 4, 5}

# Проверка подмножества
subset = {1, 2}
print(subset <= set_a)  # True (все элементы subset в set_a)
print(subset.issubset(set_a))  # То же самое

# Проверка надмножества
print(set_a >= subset)  # True
print(set_a.issuperset(subset))  # То же самое

Реальные примеры использования

Пример 1: удаление дубликатов

# Без множеств: нужен сложный код
users = ["alice", "bob", "alice", "charlie", "bob"]

unique_users_slow = []
for user in users:
    if user not in unique_users_slow:  # O(n)
        unique_users_slow.append(user)

print(unique_users_slow)  # ['alice', 'bob', 'charlie']

# С множеством: одна строка
unique_users_fast = list(set(users))
print(unique_users_fast)  # ['alice', 'bob', 'charlie']

# Примечание: порядок теряется. Если нужен порядок:
unique_users_ordered = []
seen = set()
for user in users:
    if user not in seen:  # O(1)
        seen.add(user)
        unique_users_ordered.append(user)

print(unique_users_ordered)  # ['alice', 'bob', 'charlie']

Пример 2: анализ тегов блога

# Какие теги есть во всех постах?
posts = [
    {"title": "Python Tips", "tags": {"python", "programming", "tips"}},
    {"title": "Django Guide", "tags": {"python", "django", "web"}},
    {"title": "FastAPI", "tags": {"python", "fastapi", "api"}},
]

# Общие теги во всех постах
common_tags = posts[0]["tags"]
for post in posts[1:]:
    common_tags = common_tags & post["tags"]  # Пересечение

print(f"Common tags: {common_tags}")  # {'python'}

# Все теги со всех постов
all_tags = set()
for post in posts:
    all_tags |= post["tags"]  # Объединение

print(f"All tags: {all_tags}")
# {'python', 'programming', 'tips', 'django', 'web', 'fastapi', 'api'}

# Теги, которые есть в первом, но не во втором посте
unique_to_first = posts[0]["tags"] - posts[1]["tags"]
print(f"Unique to first: {unique_to_first}")  # {'tips', 'programming'}

Пример 3: проверка прав доступа

# Какие привилегии есть у пользователя?
user_permissions = {"read", "write", "comment"}
required_permissions = {"write", "delete"}

# Проверка: есть ли все требуемые разрешения?
has_permission = required_permissions <= user_permissions
print(f"Has required permissions: {has_permission}")  # False

# Какие разрешения не хватает?
missing = required_permissions - user_permissions
print(f"Missing permissions: {missing}")  # {'delete'}

# Какие разрешения есть
available = required_permissions & user_permissions
print(f"Available permissions: {available}")  # {'write'}

Пример 4: поиск общих друзей

# Социальная сеть
users = {
    "alice": {"bob", "charlie", "david"},
    "bob": {"alice", "charlie", "eve"},
    "charlie": {"alice", "bob", "david"},
}

# Общие друзья Alice и Bob
common_friends = users["alice"] & users["bob"]
print(f"Common friends of Alice and Bob: {common_friends}")
# {'charlie'}

# Друзья Alice, которые не являются друзьями Bob
only_alice_friends = users["alice"] - users["bob"]
print(f"Only Alice's friends: {only_alice_friends}")
# {'david'}

# Рекомендация: друзья друзей Alice
friends_of_friends = set()
for friend in users["alice"]:
    friends_of_friends |= users.get(friend, set())

recommendations = friends_of_friends - users["alice"]
print(f"Recommended for Alice: {recommendations}")

Пример 5: валидация данных

# Допустимые значения статуса
valid_statuses = {"pending", "processing", "completed", "cancelled"}

# Статусы из пользовательского ввода
user_input = ["pending", "invalid_status", "completed", "unknown"]

# Какие статусы валидны?
valid_input = [status for status in user_input if status in valid_statuses]
print(f"Valid statuses: {valid_input}")
# ['pending', 'completed']

# Какие статусы невалидны?
invalid_input = set(user_input) - valid_statuses
print(f"Invalid statuses: {invalid_input}")
# {'unknown', 'invalid_status'}

frozenset — неизменяемое множество

# frozenset нельзя менять (как tuple для set)
immutable_set = frozenset({1, 2, 3})

# Можно использовать как ключ в dict или элемент другого set
set_of_sets = {frozenset({1, 2}), frozenset({2, 3})}
print(set_of_sets)  # {frozenset({1, 2}), frozenset({2, 3})}

# Мутабельный set нельзя использовать как ключ
# bad = {{1, 2}: "value"}  # TypeError: unhashable type: 'set'

Производительность

| Операция | List | Set |
|----------|------|-----|
| Добавление | O(1) | O(1) (amortized) |
| Поиск | O(n) | O(1) |
| Удаление | O(n) | O(1) |
| Пересечение | O(n*m) | O(min(n,m)) |
| Объединение | O(n+m) | O(n+m) |

Когда использовать set

✅ Используйте set когда:

• Нужна быстрая проверка принадлежности O(1)
• Нужно удалить дубликаты
• Нужны операции над множествами (объединение, пересечение)
• Порядок не важен
• Элементы уникальны

❌ Не используйте set когда:

• Нужен определённый порядок
• Нужны индексы
• Нужны дубликаты
• Нужна сортировка

Вывод

Множества (set) — это essential data structure для:

• Удаления дубликатов
• Быстрого поиска O(1)
• Операций над группами данных
• Проверки уникальности

Это один из самых недооценённых инструментов Python, но его правильное использование значительно улучшает производительность и читаемость кода.