У програмі є набір із 300 стоп-слів. Він створюється один раз і далі тільки перевіряється через in — мільйони разів. Зараз це список. Що станеться, якщо замінити його на множину?
Чому так. Множина — хеш-таблиця: адреса комірки рахується з самого значення, тому перевірка не залежить від розміру набору. На 300 елементах це вже приблизно стократна різниця, а на десятках тисяч — тисячократна. Втратити нічого не можна: стоп-слова унікальні за задумом, а якби серед них були дублікати, вони б і в списку нічого не давали.
Питання 2 / 8
Колега пише: кроки = {0: "залити воду", 1: "увімкнути", 2: "зачекати"}, пояснюючи це тим, що словник шукає за O(1). Що тут не так?
Чому так. Ключі 0, 1, 2 — це індекси, переписані вручну. Список дає той самий O(1) за індексом, займає менше памʼяті й уміє зрізи та сортування. Порядок тут ні до чого: словник зберігає порядок вставки з версії 3.7 — помилка саме у виборі структури, а не в порядку.
Питання 3 / 8
В інтерактиві «гонка пошуку» при n = 800 і режимі «елемента немає» список робить 800 порівнянь, а множина — 1. Чому саме режим «немає» найважливіший для вибору структури?
Чому так. Відповідь «немає» для списку коштує повного проходу — коротшого шляху не існує. Відповідь «є» може обійтись і одним порівнянням, але тільки якщо пощастило з позицією. Обирати структуру треба за гіршим випадком, а не за везінням. Для множини обидві відповіді коштують однаково — один крок.
Питання 4 / 8
Потрібно прибрати дублікати зі списку ["Аня", "Богдан", "Аня", "Галя"], зберігши порядок першої появи. Що взяти?
Чому так. Потрібні дві властивості одразу: унікальність і порядок. Множина дає лише першу, тому list(set(...)) і tuple(set(...)) порядок втрачають безповоротно. sorted дає абетковий порядок, а не порядок появи — це інша річ. Ключі словника мають обидві властивості, тому dict.fromkeys і став стандартною ідіомою.
Питання 5 / 8
Чому в ключ словника можна покласти кортеж, а список — ні?
Чому так. Хеш-таблиця обчислює номер комірки з ключа. Змінили ключ — змінився його хеш — запис лишився за старою адресою й став недосяжним. Python не дозволяє цьому статись, відмовляючись хешувати змінювані обʼєкти: TypeError: unhashable type: ʼlistʼ. Кортеж хешований, але не завжди — лише якщо хешовані всі його елементи.
Питання 6 / 8
Дані про оцінки зберігають як список кортежів [("Аня", 5), ("Богдан", 4), ("Аня", 3)]. Головне питання програми — «усі оцінки конкретного учня», і його ставлять тисячі разів. Що варто зробити?
Чому так. Форму даних обирають під питання, яке ставлять найчастіше. «Усі оцінки Ані» — це питання за ключем, отже, потрібен словник, у якого значення — список оцінок. Множина кортежів відповідає на інше питання («чи була така пара»), а словник з кортежем-ключем — теж на інше, і додатково злив би дві однакові оцінки в одну.
Питання 7 / 8
Що правильно про пам'ять чотирьох структур на тисячі однакових значень (CPython 3.12)?
Чому так. Список тисячі чисел — 8 056 байтів, множина — 32 984: хеш-таблиця мусить лишати вільне місце, інакше маршрути обходу колізій подовжаться й пошук перестане бути сталим. Це і є плата за швидкість. «Завжди вдвічі» неправда: обидві таблиці ростуть сходинками, і на n = 10 000 словник виявляється легшим за множину. Кортеж, навпаки, трохи легший за список — у нього немає запасу під append.
Питання 8 / 8
Що робить defaultdict(list) і в чому його єдина пастка?
Чому так. defaultdict(list) прибирає ручний setdefault: при звертанні до нового ключа він сам кладе туди порожній список. Саме тому невинна перевірка оцінки["Галя"] тихо додає «Галю» з порожнім списком — наявність треба питати через in. Порядок вставки він зберігає так само, як звичайний словник: defaultdict — його підклас.