Практика · Множини

Лекція: lecture.html · Тест: quiz.html · ДЗ: homework.md

Наскрізний приклад той самий, що в лекції: записи на день відкритих дверей і два гуртки. Тут ми руками зробимо все, про що йшлося:

1. приберемо дублікати зі списку записів;
2. переконаємось, що {} — це словник, а не порожня множина;
3. побачимо різницю між remove і discard — і зловимо справжній KeyError;
4. порахуємо, скільки кроків коштує in у списку й у множині;
5. пройдемо всі операції: |, &, -, ^ — і покажемо, що A - B і B - A різні;
6. головна перевірка практики: зберемо власний перетин через in і доведемо assert-ом, що вбудований & робить рівно те саме;
7. спробуємо покласти в множину список — і подивимось на traceback;
8. розберемось із frozenset, порядком комірок і дедуплікацією зі збереженням порядку.

Запускай клітинки згори вниз. Дві клітинки навмисно падають — це не помилка зошита, а навчальний матеріал: traceback теж треба вміти читати.

1 · Прибираємо дублікати

Найчастіше застосування множини — одним рядком дізнатися, скільки різних значень у списку. Множина не тримає повторів, тому просто перетворення списку на множину вже розв'язує задачу.

записи = ["Аня", "Богдан", "Аня", "Галя", "Богдан", "Оля", "Аня", "Галя"]

унікальні = set(записи)                 # повтори зникають самі, без жодної перевірки

print("надіслано записів:", len(записи))
print("різних людей:     ", len(унікальні))
print("сама множина:     ", sorted(унікальні), "<- сортуємо лише щоб вивід був стабільним")
print("відкинуто повторів:", len(записи) - len(унікальні))

надіслано записів: 8
різних людей:      4
сама множина:      ['Аня', 'Богдан', 'Галя', 'Оля'] <- сортуємо лише щоб вивід був стабільним
відкинуто повторів: 4

2 · Порожні фігурні дужки — це словник

Пастка, на якій спотикається кожен новачок рівно один раз. Порожня множина пишеться тільки як set(). Перевіримо типи, а не повіримо на слово.

порожній_словник = {}
порожня_множина = set()

print("type({})      ->", type(порожній_словник))
print("type(set())   ->", type(порожня_множина))
print("а от {1, 2}   ->", type({1, 2}), "— з елементами дужки вже означають множину")
print("і {1: 'а'}    ->", type({1: "а"}), "— двокрапка робить із них словник")

# конструктор set() приймає будь-що, що можна пройти елемент за елементом
print()
print('set("привіт") ->', sorted(set("привіт")), "— рядок розібрано по літерах")
print("set((1, 2, 2)) ->", set((1, 2, 2)), "— кортеж теж підходить")

type({})      -> <class 'dict'>
type(set())   -> <class 'set'>
а от {1, 2}   -> <class 'set'> — з елементами дужки вже означають множину
і {1: 'а'}    -> <class 'dict'> — двокрапка робить із них словник

set("привіт") -> ['в', 'и', 'п', 'р', 'т', 'і'] — рядок розібрано по літерах
set((1, 2, 2)) -> {1, 2} — кортеж теж підходить

3 · Додати елемент: add

add не скаржиться на повтори. Спроба додати те, що вже є, просто нічого не робить — і саме тому множину зручно наповнювати наосліп.

гурток = {"Аня", "Богдан", "Галя"}
print("на початку:", len(гурток), "учасники")

гурток.add("Оля")                       # нового імені не було — множина виросла
print("після add('Оля'):   ", len(гурток))

гурток.add("Аня")                       # це ім'я вже є — нічого не сталось, і помилки теж немає
print("після add('Аня'):   ", len(гурток), "<- розмір не змінився")
print("склад гуртка:", sorted(гурток))

на початку: 3 учасники
після add('Оля'):    4
після add('Аня'):    4 <- розмір не змінився
склад гуртка: ['Аня', 'Богдан', 'Галя', 'Оля']

4 · Перша навмисна помилка: remove на відсутньому елементі

У множині немає «Петра». remove вважає це аварією й зупиняє програму. Прочитай traceback: останній рядок називає і тип помилки, і сам елемент.

гурток.remove("Петро")

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
Cell In[4], line 1
----> 1 гурток.remove("Петро")

KeyError: 'Петро'

5 · discard — те саме питання, інша реакція

discard на відсутньому елементі мовчить. Множина лишається тією самою, і код іде далі. Перевіримо це assert-ом, а не на око.

розмір_до = len(гурток)

гурток.discard("Петро")                 # такого учасника немає — і це нормально
print("discard('Петро') відпрацював без жодного звуку")

гурток.discard("Богдан")                # а цей є — його прибрано
print("discard('Богдан') прибрав учасника")

print("було:", розмір_до, "· стало:", len(гурток))
assert len(гурток) == розмір_до - 1, "discard мав прибрати рівно одного"
print("✅ відсутній елемент не змінив нічого, наявний прибрався")
print("склад гуртка:", sorted(гурток))

discard('Петро') відпрацював без жодного звуку
discard('Богдан') прибрав учасника
було: 4 · стало: 3
✅ відсутній елемент не змінив нічого, наявний прибрався
склад гуртка: ['Аня', 'Галя', 'Оля']

6 · Скільки кроків коштує in

Порахуємо чесно. Для списку пошук — це перебір: рахуватимемо кожне порівняння вручну. Для множини кроків завжди один, скільки б елементів у ній не було.

Найважливіший випадок — коли шуканого немає: список тоді змушений переглянути все.

# великий стоп-список: слова «слово0000», «слово0001», … — рівно 2000 штук
стоп_список = []
for номер in range(2000):               # забігання наперед: цикли — тема 12
    стоп_список.append("слово%04d" % номер)

стоп_множина = set(стоп_список)         # ті самі 2000 слів, тільки інша структура

шукане = "цього-слова-тут-немає"

кроків_у_списку = 0
for слово in стоп_список:               # забігання наперед: цикли — тема 12
    кроків_у_списку += 1                # рахуємо кожне порівняння, яке робить `in`
    if слово == шукане:                 # забігання наперед: умови — тема 11
        break

print("розмір набору:      ", len(стоп_список))
print("кроків у списку:    ", кроків_у_списку, "— довелося переглянути все")
print("кроків у множині:    1 — адреса рахується з самого слова")
print()
print("відповідь однакова:", шукане in стоп_список, "==", шукане in стоп_множина)
assert (шукане in стоп_список) == (шукане in стоп_множина), "відповіді розійшлися!"
print("✅ результат той самий, роботи — у", кроків_у_списку, "разів менше")

розмір набору:       2000
кроків у списку:     2000 — довелося переглянути все
кроків у множині:    1 — адреса рахується з самого слова

відповідь однакова: False == False
✅ результат той самий, роботи — у 2000 разів менше

7 · Операції: |, &, -, ^

Два гуртки, дехто ходить в обидва. Кожна операція відповідає на своє питання. Друкуємо sorted(...), щоб вивід не залежав від порядку комірок.

робототехніка = {"Аня", "Богдан", "Галя", "Оля"}
малювання = {"Галя", "Оля", "Петро", "Ніна"}

print("A | B  об'єднання         ->", sorted(робототехніка | малювання))
print("A & B  перетин            ->", sorted(робототехніка & малювання))
print("A - B  тільки в A         ->", sorted(робототехніка - малювання))
print("A ^ B  рівно в одному     ->", sorted(робототехніка ^ малювання))
print()
print("ті самі операції словами:")
print("union        ->", sorted(робототехніка.union(малювання)))
print("intersection ->", sorted(робототехніка.intersection(малювання)))

A | B  об'єднання         -> ['Аня', 'Богдан', 'Галя', 'Ніна', 'Оля', 'Петро']
A & B  перетин            -> ['Галя', 'Оля']
A - B  тільки в A         -> ['Аня', 'Богдан']
A ^ B  рівно в одному     -> ['Аня', 'Богдан', 'Ніна', 'Петро']

ті самі операції словами:
union        -> ['Аня', 'Богдан', 'Галя', 'Ніна', 'Оля', 'Петро']
intersection -> ['Галя', 'Оля']

8 · A - B і B - A — це різні питання

Різниця множин не симетрична. «Хто ходить тільки на робототехніку» і «хто ходить тільки на малювання» — два різні набори, у яких немає жодного спільного імені.

тільки_робототехніка = робототехніка - малювання
тільки_малювання = малювання - робототехніка

print("A - B ->", sorted(тільки_робототехніка))
print("B - A ->", sorted(тільки_малювання))

assert тільки_робототехніка != тільки_малювання, "різниця раптом стала симетричною?"
assert тільки_робототехніка.isdisjoint(тільки_малювання), "у них знайшлось спільне ім'я"
print("✅ набори різні й не перетинаються — порядок операндів тут вирішує все")

# а от об'єднання й перетин від перестановки не залежать
print("A | B == B | A ->", (робототехніка | малювання) == (малювання | робототехніка))
print("A & B == B & A ->", (робототехніка & малювання) == (малювання & робототехніка))

A - B -> ['Аня', 'Богдан']
B - A -> ['Ніна', 'Петро']
✅ набори різні й не перетинаються — порядок операндів тут вирішує все
A | B == B | A -> True
A & B == B & A -> True

9 · Головна перевірка: наш перетин проти вбудованого &

Найцінніше, що дає практика, — побачити, що всередині бібліотеки немає магії. Зберемо перетин власноруч: пройдемо перший гурток і залишимо тільки тих, хто знайшовся в другому через in. Потім доведемо assert-ом, що результат збігається з тим, що дає оператор &.

власний_перетин = set()

for учасник in робототехніка:           # забігання наперед: цикли — тема 12
    if учасник in малювання:            # забігання наперед: умови — тема 11
        власний_перетин.add(учасник)    # `in` по множині — один крок, тому це дешево

бібліотечний_перетин = робототехніка & малювання

print("наш перетин:        ", sorted(власний_перетин))
print("вбудований оператор:", sorted(бібліотечний_перетин))

assert власний_перетин == бібліотечний_перетин, "наш перетин розійшовся з &!"
print("✅ збігається")

наш перетин:         ['Галя', 'Оля']
вбудований оператор: ['Галя', 'Оля']
✅ збігається

Те саме зробимо для різниці й об'єднання — щоб переконатись, що збіг не випадковий. Зверни увагу: множини порівнюються за складом, а не за порядком, тому == тут працює саме так, як нам треба.

власна_різниця = set()
for учасник in робототехніка:           # забігання наперед: цикли — тема 12
    if учасник not in малювання:        # not in — те саме питання, зворотна відповідь
        власна_різниця.add(учасник)

власне_об_єднання = set(робототехніка)  # копія, щоб не зіпсувати оригінал
власне_об_єднання.update(малювання)     # update — це і є |= для множин

print("наша різниця   ->", sorted(власна_різниця),
      "· бібліотечна ->", sorted(робототехніка - малювання))
print("наше об'єднання ->", sorted(власне_об_єднання),
      "· бібліотечне ->", sorted(робототехніка | малювання))

assert власна_різниця == робототехніка - малювання, "різниця розійшлася!"
assert власне_об_єднання == робототехніка | малювання, "об'єднання розійшлося!"
assert робототехніка == {"Оля", "Галя", "Богдан", "Аня"}, "оригінал зіпсовано"
print("✅ усі три збіглися, а вихідна множина не постраждала")

наша різниця   -> ['Аня', 'Богдан'] · бібліотечна -> ['Аня', 'Богдан']
наше об'єднання -> ['Аня', 'Богдан', 'Галя', 'Ніна', 'Оля', 'Петро'] · бібліотечне -> ['Аня', 'Богдан', 'Галя', 'Ніна', 'Оля', 'Петро']
✅ усі три збіглися, а вихідна множина не постраждала

10 · Підмножина, надмножина, isdisjoint

Знаки <= і >= для множин читаються не як «менше» й «більше», а як «міститься» й «містить». Класичне застосування — перевірка прав доступу.

потрібні_дозволи = {"читати", "писати"}
дозволи_користувача = {"читати", "писати", "видаляти"}

print("усі потрібні дозволи є?      ", потрібні_дозволи <= дозволи_користувача)
print("користувач має щось зайве?   ", дозволи_користувача > потрібні_дозволи)
print("а навпаки?                   ", дозволи_користувача <= потрібні_дозволи)

# дві множини можуть бути непорівнянними в обидва боки — для чисел таке неможливо
ліва = {1, 2}
права = {2, 3}
print()
print("{1,2} <= {2,3} ->", ліва <= права)
print("{1,2} >= {2,3} ->", ліва >= права, "<- обидві відповіді False одночасно")
print("а спільне в них є?", not ліва.isdisjoint(права), "· спільне:", sorted(ліва & права))

усі потрібні дозволи є?       True
користувач має щось зайве?    True
а навпаки?                    False

{1,2} <= {2,3} -> False
{1,2} >= {2,3} -> False <- обидві відповіді False одночасно
а спільне в них є? True · спільне: [2]

11 · Друга навмисна помилка: список у множину не покласти

Адреса елемента обчислюється з нього самого. Якщо елемент можна змінити — адреса «протухне», і елемент загубиться. Python не дає цьому статись і падає одразу.

набір = set()
набір.add(["Аня", "Богдан"])

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[12], line 2
      1 набір = set()
----> 2 набір.add(["Аня", "Богдан"])

TypeError: unhashable type: 'list'

12 · Що можна класти всередину — і що рятує frozenset

Правило те саме, що для ключів словника: хешується те, що не можна змінити. Кортеж — можна, список — ні, звичайна множина — ні, заморожена — можна.

можна = {42, "кіт", 3.14, ("Київ", "Хрещатик"), frozenset({1, 2})}
print("змішана множина зібралась, елементів:", len(можна))

# перевіримо кожен проблемний випадок і надрукуємо саму помилку
проблемні = [["список"], (1, [2]), {"словник": 1}, {1, 2}]
for елемент in проблемні:               # забігання наперед: цикли — тема 12
    try:
        hash(елемент)
        print(repr(елемент), "-> хешується")
    except TypeError as помилка:
        print(repr(елемент), "->", type(помилка).__name__, "-", помилка)

змішана множина зібралась, елементів: 5
['список'] -> TypeError - unhashable type: 'list'
(1, [2]) -> TypeError - unhashable type: 'list'
{'словник': 1} -> TypeError - unhashable type: 'dict'
{1, 2} -> TypeError - unhashable type: 'set'

frozenset — незмінна множина. Вона хешується, тому її можна покласти в іншу множину або взяти ключем словника. І ось випадок, де це єдино правильне рішення: пара учасників, для якої «Аня й Богдан» і «Богдан і Аня» — та сама пара.

пара_1 = frozenset({"Аня", "Богдан"})
пара_2 = frozenset({"Богдан", "Аня"})   # ті самі двоє, записані навпаки

різні_пари = {пара_1, пара_2}
print("поклали дві пари, у множині опинилось:", len(різні_пари))
assert len(різні_пари) == 1, "frozenset раптом почав зважати на порядок"

# для порівняння: кортежі порядок розрізняють, і пари стало б дві
кортежі = {("Аня", "Богдан"), ("Богдан", "Аня")}
print("а з кортежами було б:", len(кортежі), "<- ось чому тут потрібен саме frozenset")

# frozenset уміє все, крім зміни
оцінки = {пара_1: 11}
print("оцінка пари:", оцінки[frozenset({"Богдан", "Аня"})])
print("операції працюють:", пара_1 & {"Богдан", "Галя"})

поклали дві пари, у множині опинилось: 1
а з кортежами було б: 2 <- ось чому тут потрібен саме frozenset
оцінка пари: 11
операції працюють: frozenset({'Богдан'})

13 · Порядок задають комірки, а не ти

Для невеликих цілих hash(n) == n, тому місце кожного числа в таблиці на 8 комірок рахується просто: n % 8. Читання йде по комірках підряд — тому три різні записи однієї множини друкуються однаково.

варіант_1 = {10, 3, 25, 7}
варіант_2 = {3, 7, 10, 25}
варіант_3 = {25, 10, 7, 3}

print("записали {10, 3, 25, 7} -> надрукувалось", list(варіант_1))
print("записали {3, 7, 10, 25} -> надрукувалось", list(варіант_2))
print("записали {25, 10, 7, 3} -> надрукувалось", list(варіант_3))

print()
print("номери комірок: 25 % 8 =", 25 % 8, "· 10 % 8 =", 10 % 8,
      "· 3 % 8 =", 3 % 8, "· 7 % 8 =", 7 % 8)

assert list(варіант_1) == list(варіант_2) == list(варіант_3), "порядок раптом розійшовся"
assert list(варіант_1) == [25, 10, 3, 7], "комірки лягли не так, як очікували"
print("✅ порядок однаковий у всіх трьох — його задають комірки 1, 2, 3, 7")

# з рядками правило те саме, але хеш рядка рандомізований при кожному запуску
print()
print("а множина слів друкується щоразу по-різному:", set("абв"))
print("тому для стабільного виводу завжди беруть sorted():", sorted(set("абв")))

записали {10, 3, 25, 7} -> надрукувалось

 [25, 10, 3, 7]
записали {3, 7, 10, 25} -> надрукувалось [25, 10, 3, 7]
записали {25, 10, 7, 3} -> надрукувалось [25, 10, 3, 7]

номери комірок: 25 % 8 = 1 · 10 % 8 = 2 · 3 % 8 = 3 · 7 % 8 = 7
✅ порядок однаковий у всіх трьох — його задають комірки 1, 2, 3, 7

а множина слів друкується щоразу по-різному: {'в', 'б', 'а'}
тому для стабільного виводу завжди беруть sorted(): ['а', 'б', 'в']

14 · Дедуплікація зі збереженням порядку

set порядок втрачає — за конструкцією. Якщо порядок першої появи потрібен, беруть dict.fromkeys: ключі словника унікальні, а порядок вставки він зберігає з 3.7.

через_множину = list(set(записи))
через_словник = list(dict.fromkeys(записи))

print("вихідний список:      ", записи)
print("list(set(...)):       ", через_множину, "<- порядок втрачено")
print("list(dict.fromkeys()):", через_словник, "<- порядок першої появи")

# склад однаковий, різниця лише в порядку
assert set(через_множину) == set(через_словник), "склад розійшовся!"
assert через_словник == ["Аня", "Богдан", "Галя", "Оля"], "порядок першої появи не збігся"
print("✅ склад той самий, але порядок зберіг лише dict.fromkeys")

вихідний список:       ['Аня', 'Богдан', 'Аня', 'Галя', 'Богдан', 'Оля', 'Аня', 'Галя']
list(set(...)):        ['Богдан', 'Галя', 'Аня', 'Оля'] <- порядок втрачено
list(dict.fromkeys()): ['Аня', 'Богдан', 'Галя', 'Оля'] <- порядок першої появи
✅ склад той самий, але порядок зберіг лише dict.fromkeys

15 · Як множина росте в пам'яті

Хеш-таблиця множини не дає собі заповнитись більш ніж приблизно на три п'ятих — раніше, ніж словник із його двома третинами. Побачимо стрибок на власні очі.

import sys

множина = set()
попередній_розмір = sys.getsizeof(множина)
print("порожня множина:", попередній_розмір, "байтів (таблиця на 8 комірок уже всередині)")

for номер in range(1, 25):              # забігання наперед: цикли — тема 12
    множина.add(номер)
    розмір = sys.getsizeof(множина)
    if розмір != попередній_розмір:
        print("на %2d-му елементі розмір став %4d байтів  <- таблиця перебудувалась"
              % (номер, розмір))
        попередній_розмір = розмір

print("усього елементів:", len(множина), "· підсумковий розмір:", sys.getsizeof(множина))

порожня множина: 216 байтів (таблиця на 8 комірок уже всередині)
на  5-му елементі розмір став  728 байтів  <- таблиця перебудувалась
на 19-му елементі розмір став 2264 байтів  <- таблиця перебудувалась
усього елементів: 24 · підсумковий розмір: 2264

Завдання

🟢 Рівень 1

Візьми список записи з розділу 1 і додай до нього ще два імені, одне з яких уже там є. Надрукуй довжину списку й довжину множини після цього. Перевір assert-ом, що множина виросла рівно на одиницю, а список — на два.

🟡 Рівень 2

Дано відвідування сторінок за два дні:

вчора = ["/головна", "/ціни", "/про-нас", "/головна"]
сьогодні = ["/ціни", "/контакти", "/головна"]

Порахуй трьома окремими рядками: які сторінки дивились обидва дні, які з'явились сьогодні й які зникли. Перевір усі три результати assert-ами й поясни в коментарі, чому тут не можна обійтись одним ^.

🔴 Рівень 3

Напиши перевірку власний_симетричний(A, B), яка збирає симетричну різницю без операторів ^, - і без методу symmetric_difference — тільки через in, not in і add. Потім:

1. доведи assert-ом, що вона збігається з A ^ B на трьох різних парах множин;
2. перевір її на випадку, коли множини не перетинаються взагалі, і на випадку, коли вони рівні — і поясни, чому в другому випадку результат порожній;
3. подумай і напиши у коментарі, скільки разів твоя перевірка виконує in і чому це дешевше, ніж те саме зі списками.