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

Словники

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

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

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

1.1 · Твоя телефонна книга

Створи словник книга щонайменше з чотирма записами «ім'я → номер». Потім:

  1. надрукуй номер одного з наявних імен через квадратні дужки;
  2. надрукуй номер неіснуючого імені через .get() зі значенням за замовчуванням "немає в книзі";
  3. додай новий запис і одразу перезапиши його іншим номером;
  4. видали один запис через pop, зберігши видалений номер у змінну й надрукувавши його.

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

assert len(книга) == 4
assert книга.get("такого точно немає") is None

і жодного разу програма не впала з KeyError.

1.2 · Таблиця замість умов

Дано словник відповідностей «літера ноти → її частота в герцах»:

частоти = {"до": 261.6, "ре": 293.7, "мі": 329.6, "фа": 349.2, "соль": 392.0}

Надрукуй частоти для "мі", "соль" і для неіснуючої "сі" — останню з поясненням "такої ноти в таблиці немає". Усе через .get(), без жодної перевірки if.

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

assert len(частоти) == 5

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

2.1 · Злиття налаштувань

Є три словники: типові налаштування програми, налаштування команди й особисті налаштування користувача.

типові = {"тема": "світла", "мова": "uk", "шрифт": 14, "автозбереження": True}
командні = {"мова": "en", "шрифт": 13}
особисті = {"тема": "темна"}

Зроби новий словник підсумкові, у якому пріоритет зростає в порядку типові → командні → особисті. Вихідні три словники мають лишитися незмінними.

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

assert підсумкові == {"тема": "темна", "мова": "en", "шрифт": 13, "автозбереження": True}
assert типові["тема"] == "світла"
assert командні == {"мова": "en", "шрифт": 13}
assert len(підсумкові) == 4

і ти пояснив у коментарі одним реченням, чому саме особисті мають стояти справа.

2.2 · 🔁 Частоти літер і перевірка себе

Візьми довільний рядок щонайменше з 40 символів (наприклад, перше речення лекції). Порахуй, скільки разів трапляється кожна літера, використовуючи тільки ідіому лічильник[символ] = лічильник.get(символ, 0) + 1.

Пробіли не рахуй: прибери їх заздалегідь через рядок.replace(" ", "").

Потім порівняй свій результат із collections.Counter по тому самому рядку.

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

from collections import Counter
assert мій_лічильник == dict(Counter(текст_без_пробілів)), "розійшлося з Counter"

і ти надрукував три найчастіші літери разом із їхньою кількістю (підказка: Counter(...).most_common(3) — але спершу дістань їх зі свого словника).

2.3 · Де ламається порядок

Створи словник із чотирьох ключів. Надрукуй list(словник). Потім:

  1. зміни значення середнього ключа — надрукуй порядок знову;
  2. видали цей ключ і додай його заново з тим самим значенням — надрукуй порядок знову.

Зроблено, якщо: ти показав кодом і assert-ами, що в першому випадку порядок не змінився, а в другому ключ поїхав у кінець, і пояснив словами (2–3 речення), чому ці два випадки різні з точки зору хеш-таблиці.

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

3.1 · Своя міні-хеш-таблиця

Реалізуй хеш-таблицю на списку з 8 комірок, не використовуючи dict узагалі. Потрібні три функції:

Кожна комірка — або None, або пара [ключ, значення]. Цикли тут дозволені.

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

таблиця = [None] * 8
покласти(таблиця, "Аня", "067")
покласти(таблиця, "Богдан", "050")
покласти(таблиця, "Галя", "063")
покласти(таблиця, "Оля", "095")        # хеш 1047570, цілиться в комірку 2 — колізія

assert хеш("Аня") == 1034178
assert хеш("Оля") == 1047570
assert хеш("Оля") % 8 == 2             # та сама комірка, що в «Аня»
assert таблиця[2][0] == "Аня"          # «Аня» лишилась на місці
assert таблиця[5][0] == "Оля"          # «Оля» переїхала в комірку 5
assert взяти(таблиця, "Оля") == "095"  # і все одно знаходиться
assert взяти(таблиця, "Петро", "—") == "—"

Числа тут не випадкові: це рівно те, що показує інтерактив 4 у лекції. Якщо твої не збігаються — шукай різницю у формулі хеша.

3.2 · Скільки коштує колізія

Спираючись на 3.1, додай у покласти й взяти підрахунок спроб: скільки комірок довелося оглянути, перш ніж знайшлася потрібна.

Зроби таблицю на 8 комірок і заповнюй її ключами "к1", "к2", … по одному, щоразу друкуючи, скільки спроб пішло на вставку та яке зараз заповнення у відсотках.

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

  1. чому Python не дозволяє заповнювати таблицю більш ніж на дві третини;
  2. що станеться з взяти, якщо таблиця заповниться повністю, а шуканого ключа в ній немає (спробуй це відтворити — і полагодь так, щоб функція не зациклилась).

Підказки