Как множества работают иначе

Множества: встроены для проверок принадлежности

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

Когда ты проверяешь принадлежность, компьютер вычисляет тот же хеш & прыгает напрямую в правильное место. Без сканирования.

# A set of pets
pets = {"cat", "dog", "cat", "fish", "dog"}

print(pets)      # {"cat", "dog", "fish"} — duplicates removed
print(len(pets)) # 3 — only unique items

Заметь три отличия от списков:

1. Без дубликатов. "cat" появился дважды в входных данных, но множество хранит только одну копию.

2. Без гарантированного порядка. Множество может вывести элементы в любом расположении.

3. Нет доступа по индексу. Ты не можешь написать pets[0] — множества не имеют позиций.

Компромисс: ты теряешь порядок & дубликаты. Ты выигрываешь O(1) проверку принадлежности — проверка, находится ли элемент, занимает одно и то же время, есть ли в множестве 5 элементов или 5 миллионов.

# Membership check — is "fish" in the set?
if "fish" in pets:    # hash("fish") → jump to bucket → found
    print("found!")   # checked exactly 1 spot, not 4

Множество против списка для проверки принадлежности

У тебя есть 500 имён студентов, хранящихся в множестве вместо списка.

students = {"Alex", "Maria", ..., "Zara", ...}  # 500 names
if "Zara" in students:
    print("enrolled")

Сравнение рядом

Шпаргалка по операциям

Используй список, когда тебе нужно:

- Элементы в определённом порядке (плейлист, рецепт, очередь)

- Доступ по позиции (items[3])

- Дубликаты сохранены ("cat" появляется 3 раза = 3 кошки)

Используй множество, когда тебе нужно:

- Быстрые проверки принадлежности ("видел ли я это раньше?")

- Автоматическое удаление дубликатов

- Порядок не важен

Используй оба, когда тебе нужны порядок И быстрый поиск:

seen = set()     # O(1) membership checks
result = []      # preserves insertion order
for item in data:
    if item not in seen:  # O(1) check
        seen.add(item)    # O(1) add
        result.append(item)  # O(1) append
# Total: O(N) — one pass, each step O(1)

Этот паттерн "множество + список" даёт тебе лучшее от обоих: упорядоченные результаты с быстрым обнаружением дубликатов.

Выбери правильную структуру

Три задачи. Для каждой, решу: список, множество или оба?

1. Тебе нужно хранить плейлист песен в том порядке, в котором их добавил пользователь.

2. Тебе нужно быстро проверить, было ли имя пользователя уже занято.

3. Тебе нужно удалить дублирующиеся письма из списка рассылки, но сохранить их в порядке, в котором они зарегистрировались.

Проблема дедупликации

Задача: удалить дубликаты, сохранить порядок

Ты получаешь список подписок на письма. Некоторые люди подписались дважды. Тебе нужно отправить одно письмо за человека, в порядке, в котором они впервые подписались.

Попытка 1: только список (медленно)

signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
unique = []
for email in signups:
    if email not in unique:  # O(N) scan of unique list
        unique.append(email)
# Works! But: O(N) check × N items = O(N²)

С 100 подписками, это делает ~5000 проверок. С 10000 подписками: ~50000000 проверок.

Попытка 2: множество + список (быстро)

signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
seen = set()
unique = []
for email in signups:
    if email not in seen:   # O(1) hash lookup
        seen.add(email)     # O(1) add to set
        unique.append(email) # O(1) append to list
# O(1) check × N items = O(N)

Тот же результат. Тот же порядок. Но: 10000 подписок теперь требует ~10000 проверок вместо ~50000000.

Подсчитай ускорение

Версия со списком работает при O(N²). Версия с множеством+списком работает при O(N).

У тебя есть 10000 подписок на письма для дедупликации.

Поиск общих элементов

Задача: найди элементы в обоих списках

У тебя есть два списка учебных классов. Тебе нужно найти студентов, записанных в оба класса.

Медленный подход: вложенные циклы O(N × M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a:        # N iterations
    if student in class_b:     # M scans each time
        both.append(student)
# O(N × M) — each student scanned against all of class_b

Быстрый подход: преобразуй один список в множество O(N + M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b)     # O(M) to build
both = []
for student in class_a:        # N iterations
    if student in class_b_set: # O(1) each time
        both.append(student)
# O(N + M) — build the set once, check N times at O(1) each

Или даже проще, используя встроенное пересечение множества Python:

both = set(class_a) & set(class_b)  # O(N + M)

Оператор & находит все элементы, которые появляются в обоих множествах.

Переписать для быстроты

В школе есть два клуба с 200 членами каждый. Этот код находит студентов в обоих клубах:

chess_club = [...]   # 200 names
art_club = [...]     # 200 names
both_clubs = []
for student in chess_club:
    if student in art_club:
        both_clubs.append(student)

Твой фреймворк принятия решений

Твой фреймворк принятия решений о структурах данных

Каждый раз, когда ты пишешь код, который хранит коллекцию элементов, спроси:

1. Нужны ли мне элементы в порядке? → список

2. Нужны ли мне быстрые проверки принадлежности? → множество

3. Нужны ли мне И порядок И быстрые проверки? → множество + список вместе

4. Нужны ли мне дубликаты? → список (множества удаляют дубликаты)

---

Ключевое понимание этого урока: одна и та же программа, решающая одну и ту же задачу, может работать в 1000× или даже в 1000000× раз быстрее просто выбрав правильную структуру данных. Нет хитрых приёмов. Нет сложной математики. Просто спроси: какие операции выполняет мой код чаще всего? Потом выбери структуру, где эти операции стоят O(1) вместо O(N).

Этот урок охватил списки & множества. Существуют другие структуры данных (словари, деревья, кучи), которые решают другие задачи. Фреймворк принятия решений остаётся одинаковым: разберись в своих операциях, потом выбери структуру, которая их дешёвые.

---

Хочешь идти глубже? Наш урок Big O охватывает темпы роста & вычисления масштабирования в деталях. Смотри Big O: How Fast Is Fast Enough?. Наш курс unhamming охватывает реальный дефект (MOAD-0001), где этот точный список-в-множество прирост дал 1000× ускорение в production программном обеспечении. Смотри The Missing Chapter: Algorithmic Complexity.

Отладь этот код

Студент написал этот код для подсчёта, сколько уникальных слов появляется в книге:

words = book.split()           # list of all words
unique_count = 0
checked = []
for word in words:             # N words
    if word not in checked:    # scans checked list
        checked.append(word)
        unique_count += 1
print(unique_count)

Книга имеет 100000 слов.