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

Яку структуру обрати

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

Тема підсумкова, тож і завдання підсумкові: тут майже немає «напиши код, який працює». Майже скрізь треба обрати структуру й довести, що вибір правильний — або перевіркою властивостей, або секундоміром.

Дозволено з бібліотек: sys, time, timeit, random, collections. Більше не треба. Циклів і умов ми ще не проходили — завдання рівнів 1 і 2 розв'язуються без них, окрім позначених 🔁 (там цикл дозволений як забігання наперед у теми 11 і 12). У рівні 3 цикли, умови й функції дозволені без обмежень.

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

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

Дано журнал подій із повторами:

події = ["вхід", "перегляд", "вхід", "покупка", "перегляд", "вихід", "вхід"]

Зроби з нього список унікальних подій у порядку першої появи — одним виразом, без циклів (згадай розділ 04 лекції).

Зроблено, якщо: твій код друкує результат і проходять усі три перевірки

assert унікальні == ["вхід", "перегляд", "покупка", "вихід"]
assert унікальні[0] == події[0]
assert set(унікальні) == set(події)

і ти пояснив у коментарі одним реченням, чому list(set(події)) тут не годиться.

1.2 · Чотири вимоги — чотири структури

Для кожної з чотирьох вимог створи структуру, яка її задовольняє, і поклади туди однакові дані ["б", "а", "б", "в"] (або те, що з них виходить):

  1. потрібні порядок і повтори, вміст змінюватиметься;
  2. потрібні порядок і повтори, вміст не змінюватиметься й має бути хешованим;
  3. потрібні лише унікальні значення, порядок не важливий;
  4. потрібна відповідність «значення → скільки разів воно трапилось».

Зроблено, якщо: проходять чотири перевірки

assert len(перша) == 4 and перша[0] == "б"
assert hash(друга) is not None          # кортеж хешується, список — ні
assert len(третя) == 3
assert четверта["б"] == 2

і поруч із кожною структурою стоїть коментар: яку саме вимогу вона закриває і чого коштувала б помилка (наприклад, що саме загубилося б у пункті 3).

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

2.1 · 🔁 Одна задача, дві структури, секундомір

Зроби набір із 50 000 різних рядків-ідентифікаторів ("id00000", "id00001", …) — один раз як список, другий раз як множину. Потім заміряй через timeit час перевірки in для відсутнього значення в обох структурах.

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

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

assert час_множини < час_списку
assert результат_у_списку == результат_у_множині   # обидві дали False

і ти письмово (2–3 речення) відповів: чому ми шукаємо саме відсутнє значення, а не наявне, і що змінилося б у цифрах, якби шукане лежало першим.

2.2 · 🔁 Дві форми одних даних

Дано журнал переглядів як список кортежів:

перегляди = [("Аня", "/ціни"), ("Богдан", "/головна"), ("Аня", "/головна"),
             ("Галя", "/ціни"), ("Аня", "/ціни"), ("Богдан", "/контакти")]

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

  1. скільки різних сторінок дивилась Аня;
  2. які сторінки дивились і Аня, і Богдан;
  3. які сторінки дивилась Аня, але не дивилась Галя.

Зроблено, якщо: проходять перевірки

assert len(сторінки["Аня"]) == 2          # /ціни двічі — це одна сторінка
assert сторінки["Аня"] & сторінки["Богдан"] == {"/головна"}
assert сторінки["Аня"] - сторінки["Галя"] == {"/головна"}
assert len(перегляди) == 6                # вихідні дані не постраждали

і ти пояснив у коментарі, чому саме множина значень, а не список: що зламалося б у першій перевірці, якби замість set стояв list.

2.3 · Чесна ціна пам'яті

Поклади одні й ті самі 10 000 цілих чисел у список, кортеж, словник і множину. Надрукуй sys.getsizeof для всіх чотирьох і відношення кожного до списку.

Зроблено, якщо: твої числа збігаються з інтерактивом 6 у лекції, виконується

assert sys.getsizeof(як_множина) > sys.getsizeof(як_список)
assert sys.getsizeof(як_кортеж) < sys.getsizeof(як_список)

і ти письмово відповів на два питання: чому кортеж легший за список навіть на однакових даних, і чому на n = 10 000 словник виявився легшим за множину, хоч зберігає вдвічі більше.

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

3.1 · Дедуплікація: наївна проти правильної

Напиши дві функції, які роблять те саме — прибирають дублікати зі збереженням порядку:

Це та сама комбінація з розділу 04 лекції: беремо порядок від однієї структури, а швидкий пошук — від іншої.

Згенеруй 20 000 значень із приблизно 12–13 тисячами різних (наприклад, "id%05d" % генератор.randrange(20000)) і заміряй обидві функції.

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

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. чому точка окупності «плаває» від запуску до запуску й від машини до машини.

Підказки