Чим множини відрізняються

Множини: створені для запитань про членство

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

Коли ви перевіряєте членство, комп'ютер обчислює той же геш & миттєво стрибає в потрібне місце. Без сканування.

# 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

Множина vs список членства

У вас є 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 реєстрацій: ~50,000,000 перевірок.

Спроба 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: як швидко достатньо швидко?. Наш курс unhamming охоплює реальну дефект (MOAD-0001), де саме цей список-до-множини виправлення дав 1000× прискорення в продакшн програмному забезпеченні. Див. Пропущена глава: складність алгоритму.

Відлагодити цей код

Студент написав цей код для підрахунку того, скільки унікальних слів з'являється в книзі:

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 слів.