Домашнє завдання

Множини

Три рівні. Кожен наступний спирається на попередній, але братися можна за будь-який. Пиши в окремому файлі homework_09.py або в новому зошиті — головне, щоб код запускався й друкував результат.

Дозволено з бібліотек: sys, time. Більше нічого не треба. Циклів і умов ми ще не проходили — усі завдання розв'язуються без них, окрім позначених 🔁 (там цикл і if дозволені як забігання наперед у теми 11–12).

Одне правило на всі рівні. Множина порядку не зберігає, а хеш рядка змінюється між запусками. Тому будь-який вивід множини рядків друкуй через sorted(...), а в assert-ах порівнюй множини з множинами (== дивиться на склад, не на порядок), а не списки зі списками.

рівень 1Рівень 1 — База

1.1 · Скільки різних

Склади список щонайменше з 12 елементів, у якому є повтори, — наприклад, назви фільмів, які ти дивився за місяць, або міста, де ти був. Далі:

  1. надрукуй довжину списку;
  2. зроби з нього множину й надрукуй її довжину;
  3. надрукуй, скільки повторів було відкинуто;
  4. надрукуй сам набір різних значень через sorted(...).

Зроблено, якщо: у виводі видно всі чотири рядки, а наприкінці виконуються

assert len(унікальні) < len(мій_список)
assert len(мій_список) - len(унікальні) == кількість_повторів

і жодного разу не з'явився {} там, де мала бути порожня множина.

1.2 · Дві помилки, які треба побачити

Напиши три короткі перевірки й надрукуй результат кожної:

  1. type({}) і type(set()) — покажи, що це різні типи;
  2. discard на елементі, якого немає, — покажи assert-ом, що множина не змінилась;
  3. remove на тому самому елементі — злови помилку через try/except KeyError і надрукуй її текст.

Зроблено, якщо: програма доходить до кінця й не падає, але у виводі видно справжній KeyError та його елемент. Підказка: конструкція except KeyError as помилка: print(помилка) робить рівно це.

рівень 2Рівень 2 — Плюс

2.1 · Два дні відвідувань

Дано сирі логи (у них є повтори — це нормально, людина заходила двічі):

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

Порахуй і надрукуй чотири відповіді, кожну одним виразом над множинами:

  1. які сторінки дивились обидва дні;
  2. які сторінки з'явились сьогодні;
  3. які сторінки зникли;
  4. які сторінки дивились лише в один із двох днів.

Зроблено, якщо: виконуються всі чотири перевірки

assert спільні == {"/головна", "/ціни"}
assert зʼявились == {"/контакти"}
assert зникли == {"/про-нас"}
assert лише_в_одному == {"/контакти", "/про-нас"}

і ти пояснив у коментарі одним реченням, чому пункт 4 — це не сума пунктів 2 і 3 випадково, а завжди.

2.2 · Права доступу без жодного if

Дано:

потрібні = {"читати", "писати"}
адмін = {"читати", "писати", "видаляти", "запрошувати"}
гість = {"читати"}
редактор = {"читати", "писати"}

Для кожного з трьох користувачів надрукуй один рядок виду адмін: доступ дозволено = True. Використай тільки порівняння множин (<=, >=, <, >), без жодної перевірки if і без len.

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

Зроблено, якщо: виконуються

assert потрібні <= адмін
assert not (потрібні <= гість)
assert редактор <= потрібні and редактор >= потрібні
assert редактор == потрібні

і в коментарі сказано, чому останні два рядки — це одне й те саме твердження.

2.3 · 🔁 Скільки коштує «немає»

Побудуй список із 50 000 рядків виду "слово00000", "слово00001", … і множину з тих самих рядків. Заміряй time.perf_counter() навколо перевірки "такого-слова-немає" in ... для обох структур, повторивши перевірку 100 разів.

Зроблено, якщо: ти надрукував обидва часи й відношення між ними, а в коментарі відповів на два питання:

  1. чому ми міряємо саме випадок «слова немає», а не «слово є першим»;
  2. чому в лекції ті самі дані показані в кроках, а не в мілісекундах.

рівень 3Рівень 3 — Виклик

3.1 · Своя алгебра множин

Реалізуй чотири функції, які повторюють вбудовані операції, не використовуючи операторів |, &, -, ^ і однойменних методів. Дозволено тільки in, not in, add, set() і цикл for:

Зроблено, якщо: усі перевірки проходять на трьох різних парах множин — таких, що перетинаються частково, не перетинаються зовсім і збігаються повністю:

for A, B in [({1,2,3}, {3,4}), ({1,2}, {3,4}), ({1,2}, {1,2})]:
    assert моє_обʼєднання(A, B) == A | B
    assert мій_перетин(A, B) == A & B
    assert моя_різниця(A, B) == A - B
    assert моя_симетрична(A, B) == A ^ B
print("✅ уся алгебра збіглася")

і ти дописав у коментарі, скільки разів кожна функція виконує in залежно від розмірів a і b.

3.2 · Множина множин

Є список команд, кожна — список імен. Ті самі люди могли записатись у різному порядку:

команди = [["Аня", "Богдан"], ["Богдан", "Аня"], ["Галя", "Оля", "Петро"], ["Аня", "Галя"]]

Порахуй, скільки серед них різних команд. Пряме set(команди) не спрацює — розберись, чому саме, і полагодь це одним словом.

Далі зроби словник «команда → кількість людей у ній» і надрукуй його.

Зроблено, якщо: виконуються

assert len(різні_команди) == 3
assert frozenset({"Богдан", "Аня"}) in різні_команди
assert розміри[frozenset({"Галя", "Оля", "Петро"})] == 3

і ти пояснив у коментарі двома реченнями, чому тут потрібен саме frozenset, а не кортеж: що зламалось би, якби ключем був ("Аня", "Богдан").

3.3 · Де межа заповнення

Спираючись на розділ 15 практики, знайди експериментом, на якому за рахунком елементі множина перебудовує таблицю. Зроби те саме зі словником (додавай пари номер: номер) і надрукуй обидві послідовності «номер елемента → новий sys.getsizeof».

Зроблено, якщо: ти показав числами, що множина перебудовується раніше за словник на тому самому розмірі, і письмово відповів, чому так: у словника дірки живуть у маленькій індексній таблиці по байту на комірку, а в множини кожна дірка — повноцінна комірка. Одного речення досить, але воно має спиратись на твої числа.

Підказки