# Домашнє завдання · Яку структуру обрати > Лекція: [lecture.html](lecture.html) · Практика: [practice.ipynb](practice.ipynb) · Тест: [quiz.html](quiz.html) Три рівні. Кожен наступний спирається на попередній, але братися можна за будь-який. Пиши в окремому файлі `homework_10.py` або в новому зошиті — головне, щоб код запускався й друкував результат. Тема підсумкова, тож і завдання підсумкові: тут майже немає «напиши код, який працює». Майже скрізь треба **обрати структуру й довести, що вибір правильний** — або перевіркою властивостей, або секундоміром. Дозволено з бібліотек: `sys`, `time`, `timeit`, `random`, `collections`. Більше не треба. Циклів і умов ми ще не проходили — завдання рівнів 1 і 2 розв'язуються без них, окрім позначених 🔁 (там цикл дозволений як забігання наперед у теми 11 і 12). У рівні 3 цикли, умови й функції дозволені без обмежень. --- ## 🟢 Рівень 1 — База ### 1.1 · Дедуплікація зі збереженням порядку Дано журнал подій із повторами: ```python події = ["вхід", "перегляд", "вхід", "покупка", "перегляд", "вихід", "вхід"] ``` Зроби з нього список унікальних подій **у порядку першої появи** — одним виразом, без циклів (згадай розділ 04 лекції). **Зроблено, якщо:** твій код друкує результат і проходять усі три перевірки ```python assert унікальні == ["вхід", "перегляд", "покупка", "вихід"] assert унікальні[0] == події[0] assert set(унікальні) == set(події) ``` і ти пояснив у коментарі одним реченням, чому `list(set(події))` тут не годиться. ### 1.2 · Чотири вимоги — чотири структури Для кожної з чотирьох вимог створи структуру, яка її задовольняє, і поклади туди однакові дані `["б", "а", "б", "в"]` (або те, що з них виходить): 1. потрібні порядок і повтори, вміст змінюватиметься; 2. потрібні порядок і повтори, вміст **не** змінюватиметься й має бути хешованим; 3. потрібні лише унікальні значення, порядок не важливий; 4. потрібна відповідність «значення → скільки разів воно трапилось». **Зроблено, якщо:** проходять чотири перевірки ```python assert len(перша) == 4 and перша[0] == "б" assert hash(друга) is not None # кортеж хешується, список — ні assert len(третя) == 3 assert четверта["б"] == 2 ``` і поруч із кожною структурою стоїть коментар: **яку саме вимогу** вона закриває і чого коштувала б помилка (наприклад, що саме загубилося б у пункті 3). --- ## 🟡 Рівень 2 — Плюс ### 2.1 · 🔁 Одна задача, дві структури, секундомір Зроби набір із 50 000 різних рядків-ідентифікаторів (`"id00000"`, `"id00001"`, …) — один раз як список, другий раз як множину. Потім заміряй через `timeit` час перевірки `in` для **відсутнього** значення в обох структурах. Надрукуй три числа: час для списку, час для множини й відношення. **Зроблено, якщо:** виконується ```python assert час_множини < час_списку assert результат_у_списку == результат_у_множині # обидві дали False ``` і ти письмово (2–3 речення) відповів: чому ми шукаємо саме **відсутнє** значення, а не наявне, і що змінилося б у цифрах, якби шукане лежало першим. ### 2.2 · 🔁 Дві форми одних даних Дано журнал переглядів як список кортежів: ```python перегляди = [("Аня", "/ціни"), ("Богдан", "/головна"), ("Аня", "/головна"), ("Галя", "/ціни"), ("Аня", "/ціни"), ("Богдан", "/контакти")] ``` Побудуй з нього **словник із множинами**: ім'я → множина сторінок, які ця людина відкривала. Потім дай відповідь на три питання й підтверди кожну `assert`-ом: 1. скільки різних сторінок дивилась Аня; 2. які сторінки дивились **і** Аня, **і** Богдан; 3. які сторінки дивилась Аня, але не дивилась Галя. **Зроблено, якщо:** проходять перевірки ```python assert len(сторінки["Аня"]) == 2 # /ціни двічі — це одна сторінка assert сторінки["Аня"] & сторінки["Богдан"] == {"/головна"} assert сторінки["Аня"] - сторінки["Галя"] == {"/головна"} assert len(перегляди) == 6 # вихідні дані не постраждали ``` і ти пояснив у коментарі, чому саме **множина** значень, а не список: що зламалося б у першій перевірці, якби замість `set` стояв `list`. ### 2.3 · Чесна ціна пам'яті Поклади одні й ті самі 10 000 цілих чисел у список, кортеж, словник і множину. Надрукуй `sys.getsizeof` для всіх чотирьох і відношення кожного до списку. **Зроблено, якщо:** твої числа збігаються з інтерактивом 6 у лекції, виконується ```python assert sys.getsizeof(як_множина) > sys.getsizeof(як_список) assert sys.getsizeof(як_кортеж) < sys.getsizeof(як_список) ``` і ти письмово відповів на два питання: чому кортеж легший за список навіть на однакових даних, і чому на `n = 10 000` словник виявився **легшим** за множину, хоч зберігає вдвічі більше. --- ## 🔴 Рівень 3 — Виклик ### 3.1 · Дедуплікація: наївна проти правильної Напиши дві функції, які роблять те саме — прибирають дублікати зі збереженням порядку: - `через_список(послідовність)` — тримає лише список результату й перевіряє `if елемент not in результат`; - `через_множину(послідовність)` — тримає **дві** структури: список результату (для порядку) і множину вже побачених (для швидкої перевірки). Це та сама комбінація з розділу 04 лекції: беремо порядок від однієї структури, а швидкий пошук — від іншої. Згенеруй 20 000 значень із приблизно 12–13 тисячами різних (наприклад, `"id%05d" % генератор.randrange(20000)`) і заміряй обидві функції. **Зроблено, якщо:** виконуються перевірки ```python assert через_список(дані) == через_множину(дані) # результат ідентичний assert час_через_множину * 100 < час_через_список # різниця більш ніж стократна ``` і ти пояснив письмово, звідки береться саме така різниця: скільки разів кожна функція виконує перевірку `in` і скільки коштує одна така перевірка в кожному випадку. Назви складність обох функцій у O-нотації. ### 3.2 · Скільки запитів окупають множину Ходить приказка, що «на маленьких наборах список швидший за множину». Перевір її чесно — і з'ясуй, у чому вона права, а в чому ні. Спершу поміряй пошук. Візьми розміри 2, 5, 10, 20, 50, 100, 500 і 2000 елементів (елементи — рядки, не короткі числа) і для кожного заміряй через `timeit` перевірку `in` для **відсутнього** значення в списку й у множині. Надрукуй таблицю: розмір, час списку, час множини, відношення. Потім поміряй **побудову**. Для набору з 300 рядків заміряй чотири величини: час `list(дані)`, час `set(дані)`, час одного запиту до списку й до множини. Порахуй точку окупності: ``` скільки_запитів = (час_set − час_list) / (запит_у_списку − запит_у_множині) ``` Не забудь про чистоту експерименту: `timeit` треба давати щонайменше 100 000 повторів, інакше на маленьких розмірах у результат потрапить сам шум вимірювання. **Зроблено, якщо:** надруковані обидві таблиці й обчислена точка окупності, і ти письмово відповів на три питання: 1. чи знайшовся розмір, на якому список виграє в пошуку, — і чому результат саме такий (підказка: скільки порівнянь робить список і скільки коштує один хеш короткого рядка); 2. у якому єдиному сценарії список чесно виграє множину; 3. чому точка окупності «плаває» від запуску до запуску й від машини до машини. --- ## Підказки - **`dict.fromkeys` — не трюк, а прямий наслідок теми 08.** Ключі словника унікальні й зберігають порядок вставки. Обидві властивості разом більше ніде не зустрічаються, тому ця ідіома й стала стандартною. - **Не заміряй `set(список)` усередині вимірювання.** У 2.1 і 3.2 множину треба побудувати **до** `timeit`, інакше ти міряєш побудову таблиці, а не пошук у ній — і множина «програє» з абсолютно неправильних причин. - **`timeit` бере оточення явно.** Найпростіше передати `globals={...}` зі змінними, які потрібні виразу: `timeit.timeit("х in набір", globals={"х": х, "набір": набір}, number=100_000)`. Не забудь поділити результат на `number`. - **У 2.2 порівнюй множини з множинами.** `{"/головна"}` — це множина з одного елемента, а не рядок у дужках. Якщо перевірка не проходить, спершу надрукуй обидві частини порівняння й подивись на їхні типи. - **У 3.1 не бійся двох структур одразу.** Тримати список і множину з тим самим вмістом — не марнотратство, а звичайний прийом: пам'ять дешевша за час. Саме так усередині влаштована половина бібліотечного коду.