Модуль 9 · Урок 35 із 58
Data structure choice: list, deque, dict, set і Counter
Структуру даних обирають не за звичкою, а за домінантними операціями й потрібними гарантіями. Та сама колекція може бути чудовою для append і невдалою для queue-from-left або частих membership checks.
Безпечна algorithm-практика модуля 9
Пакет містить тільки synthetic tasks і graph, deterministic operation counts, локальний Python CLI, tests та read-only verifier. Жодних персональних чи production-даних, credentials, мережевих викликів, machine paths або зовнішніх залежностей.
Спочатку workload matrix
Запишіть, що робить система частіше: indexed read, append, pop-left, exact lookup, membership, counting, stable iteration чи sorted range. Потім зіставте операції з гарантіями структури. Big O не є єдиним критерієм: семантика, memory, order і простота перевірки так само важливі.
| Потреба | Кандидат | Головна межа |
|---|---|---|
| Послідовність + index | list | Insert/pop біля початку пересуває елементи |
| FIFO з обох кінців | deque | Random middle access не є її силою |
| Key → value | dict | Hashable keys, average ≠ worst |
| Unique membership | set | Порядок не є sorted contract |
| Частоти | Counter | Нульове значення не видаляє key |
List і hidden linear work
Append та pop-right відповідають array-like layout, а pop(0) і insert на початку пересувають решту елементів. Slice створює нову послідовність. Якщо queue постійно бере перший елемент list, код може накопичити quadratic work на повному workload.
Не оптимізуйте один рядок без сценарію
Один pop(0) на 20 елементах не є аварією. Проблема з’являється, коли операція повторюється в циклі над зростаючою чергою.
Deque для FIFO, stack і bounded history
collections.deque підтримує append/pop з обох боків із приблизно однаковим O(1) performance. Це природна основа для BFS queue та bounded recent history через maxlen. Stack також можна реалізувати list, якщо працювати тільки з правим краєм.
from collections import deque
queue = deque(["case-01"])
queue.append("case-02")
current = queue.popleft()Dict, set і hash assumptions
Dict дає identity map, set — unique membership. Average exact lookup часто O(1), але це твердження має assumptions про hash behavior. Побудова index теж коштує time і memory, тому для одного lookup на малому input linear scan може бути простішим. Для повторних lookup index виправдовує setup.
Counter як явний frequency contract
Counter — dict subclass для hashable elements. Він добре виражає tally, але missing key повертає zero, а key із count zero лишається, доки його не видалити. Для звіту важливо визначити, чи показувати zero/negative counts і як розв’язувати ties у most_common.
- Перевірити element normalization до counting.
- Не змішувати absent і explicitly zero без правила.
- Сортувати звіт explicit key, якщо потрібна повна determinism.
- Тестувати duplicate, empty і unknown category.
Методичні джерела
Урок, сценарії, пояснення й вправи створені SEOWORK. Посилання ведуть лише на офіційну документацію та Python Wiki.
Закріпіть матеріал уроку
Три сценарні питання. Для зарахування уроку потрібно дати щонайменше дві правильні відповіді.