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

Лекція: lecture.html · Тест: quiz.html · ДЗ: homework.md

Це підсумкова практика блоку про колекції. Нових конструкцій тут не буде — буде вибір між чотирма вже знайомими структурами. Наскрізний приклад один: журнал відвідувань сайту — довгий список ідентифікаторів користувачів, у якому багато повторів.

Що зробимо:

1. розвʼяжемо одну задачу двома структурами й переконаємось, що відповідь однакова;
2. поміряємо, у скільки саме разів відрізняється ціна цієї однакової відповіді;
3. приберемо дублікати зі збереженням порядку — те, чого множина не вміє;
4. перекладемо одні дані з форми «список кортежів» у форму «словник зі списками»;
5. подивимось, чому кортеж можна покласти в ключ, а список — ні;
6. поміряємо памʼять усіх чотирьох контейнерів на однакових даних;
7. познайомимось із Counter, defaultdict і deque з модуля collections.

Кожен висновок перевіряємо через assert: він мовчить, коли все правильно, і зупиняє зошит, коли ні.

1 · Дані: журнал відвідувань

Спершу зберемо дані, з якими працюватимемо. Зерно генератора зафіксоване, тому в тебе вийдуть рівно ті самі числа, що й тут.

import random

генератор = random.Random(42)   # фіксоване зерно — щоб результат був відтворюваний

журнал = []
for _ in range(5000):           # забігання наперед: цикли — тема 12
    журнал.append("user%03d" % генератор.randrange(300))

print("подій у журналі:", len(журнал))
print("перші пʼять:    ", журнал[:5])
print("різних людей:   ", len(set(журнал)))

подій у журналі: 5000
перші пʼять:     ['user057', 'user012', 'user140', 'user125', 'user114']
різних людей:    300

2 · Одна задача — дві структури

Задача: перевірити, чи є користувач у чорному списку. Запишемо той самий чорний список двічі — як list і як set — і поставимо їм однакове питання.

Головне, що треба побачити: відповідь абсолютно однакова. Структура не змінює результат, вона змінює тільки ціну.

чорний_список = ["user007", "user013", "user042", "user099", "user123"]
чорна_множина = set(чорний_список)      # ті самі пʼять рядків, інша структура

print("список: ", чорний_список)
print("множина:", sorted(чорна_множина))

у_списку = "user042" in чорний_список
у_множині = "user042" in чорна_множина
print()
print('"user042" in чорний_список ->', у_списку)
print('"user042" in чорна_множина ->', у_множині)

assert у_списку == у_множині, "структури дали різні відповіді — так бути не може!"
print("✅ відповіді збігаються: різниця не в результаті, а в роботі")

список:  ['user007', 'user013', 'user042', 'user099', 'user123']
множина: ['user007', 'user013', 'user042', 'user099', 'user123']

"user042" in чорний_список -> True
"user042" in чорна_множина -> True
✅ відповіді збігаються: різниця не в результаті, а в роботі

3 · Скільки роботи довелося зробити

Оператор in у списку йде зліва направо, поки не натрапить на потрібне. Метод .index() показує, на якій саме позиції елемент знайшовся, — а отже, і скільки порівнянь довелося зробити.

Зверни увагу на останній рядок: найдорожчий випадок — коли елемента немає. Тоді список зобовʼязаний переглянути все до кінця.

позиція = чорний_список.index("user123")
print('"user123" стоїть на позиції', позиція)
print("отже, список зробив", позиція + 1, "порівнянь — по одному на кожен елемент до нього")

print()
print('"user500" in чорний_список ->', "user500" in чорний_список,
      "· а щоб це стверджувати, довелось перевірити всі", len(чорний_список))
print("множина в обох випадках робить один крок: рахує хеш і дивиться в одну комірку")

"user123" стоїть на позиції 4
отже, список зробив 5 порівнянь — по одному на кожен елемент до нього

"user500" in чорний_список -> False · а щоб це стверджувати, довелось перевірити всі 5
множина в обох випадках робить один крок: рахує хеш і дивиться в одну комірку

4 · Справжній секундомір

Пʼять елементів — це нічого. Візьмімо сто тисяч і поміряємо час модулем timeit (він виконує вираз багато разів і ділить сумарний час на кількість).

Шукаємо навмисно відсутній елемент: це найчастіший випадок у житті й найгірший для списку.

import timeit

великий_список = []
for номер in range(100_000):            # забігання наперед: цикли — тема 12
    великий_список.append("user%06d" % номер)

велика_множина = set(великий_список)    # ті самі сто тисяч рядків
відсутній = "такого-користувача-немає"

# timeit виконує рядок коду в переданому оточенні; ділимо на кількість повторів
оточення = {"великий_список": великий_список,
            "велика_множина": велика_множина,
            "відсутній": відсутній}

час_списку = timeit.timeit("відсутній in великий_список", globals=оточення, number=200) / 200
час_множини = timeit.timeit("відсутній in велика_множина", globals=оточення, number=200_000) / 200_000

print("список:  %9.3f мкс на одну перевірку" % (час_списку * 1e6))
print("множина: %9.3f мкс на одну перевірку" % (час_множини * 1e6))
print("множина швидша приблизно в", round(час_списку / час_множини), "разів")

assert час_множини < час_списку, "на 100 000 елементів множина не мала б програвати"
print("✅ те саме питання, та сама відповідь, різниця в тисячі разів")

список:   2527.136 мкс на одну перевірку
множина:     0.023 мкс на одну перевірку
множина швидша приблизно в 110669 разів
✅ те саме питання, та сама відповідь, різниця в тисячі разів

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

У темі 09 ми прибирали дублікати через set() — і втрачали порядок. Ось обіцяне виправлення: dict.fromkeys() будує словник, де ключі — це елементи послідовності. Ключі унікальні (дублікати злилися) і зберігають порядок вставки.

Порядок set() залежить від хешів, а хеш рядка змінюється між запусками Python — тому другий рядок виводу в тебе майже напевно буде інший. Це не помилка, це і є «порядку немає».

записи = ["Аня", "Богдан", "Аня", "Галя", "Богдан", "Оля", "Аня"]

через_множину = list(set(записи))
через_словник = list(dict.fromkeys(записи))

print("вихідні записи:  ", записи)
print("через set():     ", через_множину, " <- порядок довільний")
print("через fromkeys():", через_словник, " <- порядок першої появи")

assert set(через_множину) == set(через_словник), "склад унікальних розійшовся!"
assert через_словник == ["Аня", "Богдан", "Галя", "Оля"], "порядок першої появи не збережено"
print("✅ склад однаковий в обох, але порядок зберіг лише словник")

вихідні записи:   ['Аня', 'Богдан', 'Аня', 'Галя', 'Богдан', 'Оля', 'Аня']
через set():      ['Аня', 'Оля', 'Богдан', 'Галя']  <- порядок довільний
через fromkeys(): ['Аня', 'Богдан', 'Галя', 'Оля']  <- порядок першої появи
✅ склад однаковий в обох, але порядок зберіг лише словник

6 · Дві форми тих самих даних

Оцінки природно приходять парами «хто → скільки», тобто списком кортежів. Але питання до них найчастіше ставлять інше: «усі оцінки Ані». Під це питання зручніша форма словник зі списками.

Перекладемо дані з однієї форми в іншу. Метод setdefault тут потрібен, щоб під ключем гарантовано вже лежав список, у який можна дописувати.

оцінки_список = [("Аня", 5), ("Богдан", 4), ("Аня", 3), ("Галя", 5), ("Богдан", 2)]

оцінки_словник = {}
for імʼя, бал in оцінки_список:         # забігання наперед: цикли — тема 12
    оцінки_словник.setdefault(імʼя, []).append(бал)

print("список кортежів:    ", оцінки_список)
print("словник зі списками:", оцінки_словник)
print()
print("порядок надходження видно лише в першій формі:", оцінки_список[0], "було найпершим")
print("а швидко знайти людину дає лише друга")

список кортежів:     [('Аня', 5), ('Богдан', 4), ('Аня', 3), ('Галя', 5), ('Богдан', 2)]
словник зі списками: {'Аня': [5, 3], 'Богдан': [4, 2], 'Галя': [5]}

порядок надходження видно лише в першій формі: ('Аня', 5) було найпершим
а швидко знайти людину дає лише друга

7 · Одне питання, дві ціни

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

# форма 1: перебираємо весь список пар
анині_перебором = []
for імʼя, бал in оцінки_список:         # забігання наперед: цикли — тема 12
    if імʼя == "Аня":                   # забігання наперед: умови — тема 11
        анині_перебором.append(бал)

# форма 2: одне звертання за ключем
анині_за_ключем = оцінки_словник["Аня"]

print("перебором списку кортежів:", анині_перебором,
      "· переглянуто пар:", len(оцінки_список))
print("за ключем словника:       ", анині_за_ключем, "· переглянуто пар: 0")

assert анині_перебором == анині_за_ключем, "дві форми дали різні оцінки!"
print("✅ відповідь та сама — відрізняється лише ціна")

перебором списку кортежів: [5, 3] · переглянуто пар: 5
за ключем словника:        [5, 3] · переглянуто пар: 0
✅ відповідь та сама — відрізняється лише ціна

8 · Множина кортежів

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

відвідані = {(0, 0), (1, 2), (0, 0), (3, 1)}   # чотири пари, одна з них повторюється

print("додали 4 пари, у множині лишилось:", len(відвідані))
print("вміст:", sorted(відвідані))
print("(1, 2) вже відвідана?", (1, 2) in відвідані)
print("(9, 9) вже відвідана?", (9, 9) in відвідані)

assert len(відвідані) == 3, "дублікат (0, 0) мав злитися сам"
print("✅ унікальність безкоштовна, перевірка — один крок")

додали 4 пари, у множині лишилось: 3
вміст: [(0, 0), (1, 2), (3, 1)]
(1, 2) вже відвідана? True
(9, 9) вже відвідана? False
✅ унікальність безкоштовна, перевірка — один крок

9 · Незмінність як перепустка

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

координата = (50.45, 30.52)             # широта й довгота — кортеж, а не список
міста = {(50.45, 30.52): "Київ", (49.84, 24.03): "Львів"}

print("hash(координата) =", hash(координата))
print("міста[(50.45, 30.52)] ->", міста[(50.45, 30.52)])
print("а такої точки немає:", міста.get((0.0, 0.0), "невідоме місце"))
print("✅ кортеж працює ключем, бо його неможливо змінити після вставки")

hash(координата) = -2200792999891765937
міста[(50.45, 30.52)] -> Київ
а такої точки немає: невідоме місце
✅ кортеж працює ключем, бо його неможливо змінити після вставки

10 · Навмисна помилка: список ключем бути не може

Той самий вміст, тільки в квадратних дужках, — і Python зупиняє програму. Це не примха, а запобіжник: змінили б список після вставки — і запис загубився б назавжди. Прочитай останній рядок traceback уважно.

міста_зі_списком = {[50.45, 30.52]: "Київ"}

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[10], line 1
----> 1 міста_зі_списком = {[50.45, 30.52]: "Київ"}

TypeError: unhashable type: 'list'

11 · Скільки важить кожен контейнер

Покладемо одну й ту саму тисячу значень у всі чотири структури й поміряємо sys.getsizeof. Важливо: ця функція міряє лише контейнер. Самі числа лежать окремо, і в усіх чотирьох це ті самі обʼєкти.

Числа мають збігтися з інтерактивом 6 у лекції.

import sys

значення = range(1000)                  # тисяча цілих чисел

як_список = list(значення)
як_кортеж = tuple(значення)
як_словник = {}
for число in значення:                  # забігання наперед: цикли — тема 12
    як_словник[число] = число
як_множина = set(значення)

print("однакова тисяча значень, sys.getsizeof:")
print("  список: %6d Б" % sys.getsizeof(як_список))
print("  кортеж: %6d Б" % sys.getsizeof(як_кортеж))
print("  словник:%6d Б" % sys.getsizeof(як_словник))
print("  множина:%6d Б" % sys.getsizeof(як_множина))
print()
print("множина важча за список у %.1f раза" % (sys.getsizeof(як_множина) / sys.getsizeof(як_список)))

assert sys.getsizeof(як_множина) > sys.getsizeof(як_список), "хеш-таблиця мала б бути важчою"
print("✅ вільні комірки — це і є плата за пошук, що не залежить від розміру")

однакова тисяча значень, sys.getsizeof:
  список:   8056 Б
  кортеж:   8040 Б
  словник: 36952 Б
  множина: 32984 Б

множина важча за список у 4.1 раза
✅ вільні комірки — це і є плата за пошук, що не залежить від розміру

12 · Бонус для допитливих: словник з рядковими ключами легший

Той самий словник на тисячу записів, але ключі — рядки, а не числа. З CPython 3.6 для словників, у яких усі ключі рядки, використовується коротший формат запису: рядок сам памʼятає свій хеш, тому окремо його зберігати не треба.

рядкові_ключі = {}
for номер in range(1000):               # забігання наперед: цикли — тема 12
    рядкові_ключі["user%06d" % номер] = номер

print("словник з цілими ключами:   %6d Б" % sys.getsizeof(як_словник))
print("словник з рядковими ключами:%6d Б" % sys.getsizeof(рядкові_ключі))
print("різниця:", sys.getsizeof(як_словник) - sys.getsizeof(рядкові_ключі), "байтів на однаковій кількості записів")
print("висновок: «скільки важить словник» — питання без однієї відповіді, треба міряти свої дані")

словник з цілими ключами:    36952 Б
словник з рядковими ключами: 26032 Б
різниця: 10920 байтів на однаковій кількості записів
висновок: «скільки важить словник» — питання без однієї відповіді, треба міряти свої дані

13 · Counter: лічильник, який рахує сам

Найчастіше питання до журналу відвідувань — «хто заходив найбільше». Робити це руками через .get(ключ, 0) + 1 ми вміємо з теми 08. Counter робить те саме одним рядком — і ми зараз перевіримо, що результат той самий.

from collections import Counter

скільки_разів = Counter(журнал)
трійка_лідерів = скільки_разів.most_common(3)
найактивніший = трійка_лідерів[0][0]

print("найактивніші троє:", трійка_лідерів)
print()
print("перевіряємо лідера перебором усього списку:")
print("  журнал.count(%r) = %d" % (найактивніший, журнал.count(найактивніший)))
print("  Counter каже       %d" % скільки_разів[найактивніший])

assert скільки_разів[найактивніший] == журнал.count(найактивніший), "Counter розійшовся з count()!"
print("✅ той самий результат, але Counter порахував усіх за один прохід")
print()
print("а ще відсутній ключ дає 0, а не KeyError:", скільки_разів["user999"])

найактивніші троє: [('user169', 31), ('user135', 28), ('user058', 26)]

перевіряємо лідера перебором усього списку:
  журнал.count('user169') = 31
  Counter каже       31
✅ той самий результат, але Counter порахував усіх за один прохід

а ще відсутній ключ дає 0, а не KeyError: 0

14 · defaultdict і його пастка

defaultdict(list) — це та сама комбінація «словник зі списками» з розділу 6, тільки без ручного setdefault. Ціна — одна тиха особливість: звертання до відсутнього ключа його створює. Подивись на останній рядок.

from collections import defaultdict

оцінки_авто = defaultdict(list)
оцінки_авто["Аня"].append(5)    # ключа не було — зʼявився з порожнім списком
оцінки_авто["Аня"].append(3)
оцінки_авто["Богдан"].append(4)

print("зібралось саме:", dict(оцінки_авто))
print('"Галя" в словнику?', "Галя" in оцінки_авто)

оцінки_авто["Галя"]             # просто прочитали — і цим створили запис!
print('після простого читання "Галя" в словнику?', "Галя" in оцінки_авто)
print("тепер там:", dict(оцінки_авто))

assert "Галя" in оцінки_авто, "читання відсутнього ключа мало створити запис"
print("⚠️  саме тому перевіряй наявність через `in`, а не через звертання")

зібралось саме: {'Аня': [5, 3], 'Богдан': [4]}
"Галя" в словнику? False
після простого читання "Галя" в словнику? True
тепер там: {'Аня': [5, 3], 'Богдан': [4], 'Галя': []}
⚠️  саме тому перевіряй наявність через `in`, а не через звертання

15 · deque: дешевий з обох кінців

У списку insert(0, x) зсуває всі елементи. У deque додавання зліва коштує стільки ж, скільки справа. Плата — доступ до середини перестає бути сталим.

from collections import deque

черга = deque(["друге", "третє"])
черга.appendleft("перше")       # у списку це коштувало б зсуву всіх елементів
черга.append("четверте")

print("черга:", list(черга))
print("popleft() ->", черга.popleft(), "· лишилось:", list(черга))
print("pop()     ->", черга.pop(), "· лишилось:", list(черга))
print("довжина:", len(черга))

черга: ['перше', 'друге', 'третє', 'четверте']
popleft() -> перше · лишилось: ['друге', 'третє', 'четверте']
pop()     -> четверте · лишилось: ['друге', 'третє']
довжина: 2

16 · Підсумкова перевірка: хто що зберігає

Один і той самий набір значень із повтором — і три структури, які поводяться з ним по-різному. Це вся таблиця з розділу 01 лекції, стиснута у чотири рядки коду.

проба = ["б", "а", "б", "в"]

print("список :", проба, "· len =", len(проба))
print("кортеж :", tuple(проба), "· len =", len(tuple(проба)))
print("множина:", sorted(set(проба)), "· len =", len(set(проба)))

assert len(set(проба)) == 3, "множина мала злити другий «б»"
assert проба[0] == "б", "список зобовʼязаний зберігати порядок"
assert tuple(проба) == ("б", "а", "б", "в"), "кортеж зберігає і порядок, і повтори"
print()
print("✅ список і кортеж зберегли порядок і повтор; множина не зберегла нічого з цього")
print("   вибір між ними — це вибір того, що саме тобі потрібно зберегти")

список : ['б', 'а', 'б', 'в'] · len = 4
кортеж : ('б', 'а', 'б', 'в') · len = 4
множина: ['а', 'б', 'в'] · len = 3

✅ список і кортеж зберегли порядок і повтор; множина не зберегла нічого з цього
   вибір між ними — це вибір того, що саме тобі потрібно зберегти

Завдання

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

Візьми журнал із розділу 1 і зроби дві речі:

1. побудуй список унікальних користувачів зі збереженням порядку першої появи;
2. перевір assert, що в ньому 300 елементів, що перший елемент дорівнює журнал[0] і що склад збігається зі складом set(журнал).

Зроблено, якщо: усі три assert мовчать, а print показує перші пʼять унікальних користувачів у порядку появи.

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

Дано список подій [("Аня", "/ціни"), ("Богдан", "/головна"), ("Аня", "/головна"), …] (зроби його з десяти пар самостійно). Побудуй словник зі множинами: імʼя → множина сторінок, які ця людина відкривала.

Потім дай відповідь на два питання й підтверди їх assert:

• скільки різних сторінок дивилась Аня;
• які сторінки дивились і Аня, і Богдан (підказка: це перетин двох множин).

Зроблено, якщо: вибрано саме множину, а не список (поясни в коментарі одним реченням, чому), і обидва assert проходять.

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

Поміряй, де саме проходить межа, за якою множина починає вигравати в списку.

Візьми розміри 5, 10, 20, 50, 100 і 1000 елементів. Для кожного розміру поміряй через timeit час перевірки in для списку й для множини — шукай елемент, якого немає. Надрукуй таблицю з відношенням часів.

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

Підказки

• Для першого рівня згадай dict.fromkeys із розділу 5 — там уже все є.
• Порівнювати «склад» двох колекцій найпростіше через set(...) == set(...).
• У третьому рівні зручно тримати розміри у списку й пройтись по ньому циклом (цикли — тема 12, але вони вже траплялись у цьому зошиті).