Python · Синтаксис · Проміжний

collections: Counter, defaultdict, namedtuple

10 завдань

Спеціалізовані типи контейнерів: Counter для підрахунку, defaultdict для згрупованих даних, namedtuple для структурованих записів.

Короткий вступ до теми та пояснення перед вправами (вправи нижче):

Counter та defaultdict

#
Модуль `collections` надає спеціалізовані контейнерні типи, що вирішують поширені задачі чистіше, ніж звичайні dict та list. **Counter — підрахунок входжень** ```python from collections import Counter words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple'] c = Counter(words) # Counter({'apple': 3, 'banana': 2, 'cherry': 1}) c['apple'] # 3 c['mango'] # 0 — відсутні ключі повертають 0, а не KeyError c.most_common(2) # [('apple', 3), ('banana', 2)] c.total() # 6 (Python 3.10+) # Підрахунок символів у рядку Counter('mississippi') # Counter({'s': 4, 'i': 4, 'p': 2, 'm': 1}) ``` **Арифметика Counter** ```python a = Counter({'cat': 3, 'dog': 2}) b = Counter({'dog': 1, 'bird': 2}) a + b # Counter({'cat': 3, 'dog': 3, 'bird': 2}) — об'єднання (сума) a - b # Counter({'cat': 3, 'dog': 1}) — різниця (відкидає від'ємні) a & b # Counter({'dog': 1}) — перетин (мінімум) a | b # Counter({'cat': 3, 'bird': 2, 'dog': 2}) — об'єднання (максимум) ``` **defaultdict — автоматичні значення за замовчуванням** `defaultdict` викликає фабричну функцію для створення відсутніх значень замість генерації `KeyError`: ```python from collections import defaultdict # Групування слів за першою літерою by_letter = defaultdict(list) # фабрика: list -> за замовчуванням [] for word in ['apple', 'avocado', 'banana', 'blueberry']: by_letter[word[0]].append(word) # defaultdict({'a': ['apple', 'avocado'], 'b': ['banana', 'blueberry']}) # Підрахунок без Counter freq = defaultdict(int) # фабрика: int -> за замовчуванням 0 for ch in 'hello world': freq[ch] += 1 # Вкладені словники graph = defaultdict(set) # список суміжності для графа graph['A'].add('B') graph['A'].add('C') ``` **defaultdict vs dict.get vs dict.setdefault** ```python d = {} # Звичайний dict — три підходи до відсутніх ключів: d.get('key', 0) + 1 # читання з дефолтом, але не зберігає його d.setdefault('key', []).append(1) # зберігає дефолт при першому доступі # defaultdict — найчистіший коли всі відсутні ключі мають однаковий тип dd = defaultdict(list) dd['key'].append(1) # не потрібна спеціальна обробка ```

deque (з maxlen) та namedtuple

#
**deque — двостороння черга** `deque` (вимовляється 'дек') підтримує O(1) додавання і видалення з обох кінців. У звичайному списку `insert(0, x)` і `pop(0)` — O(n), бо всі елементи зсуваються. ```python from collections import deque d = deque([1, 2, 3]) d.append(4) # [1, 2, 3, 4] — додати праворуч d.appendleft(0) # [0, 1, 2, 3, 4] — додати ліворуч, O(1) d.pop() # 4, d = [0, 1, 2, 3] d.popleft() # 0, d = [1, 2, 3] d.rotate(1) # [3, 1, 2] — обертання праворуч на 1 d.rotate(-1) # [1, 2, 3] — обертання ліворуч на 1 ``` **maxlen — ковзне вікно / буфер фіксованого розміру** Коли `deque` має `maxlen`, нові елементи автоматично витісняють старі з іншого кінця: ```python # Зберігати останні 5 введених команд history = deque(maxlen=5) for cmd in ['ls', 'cd /tmp', 'cat file', 'pwd', 'ls -la', 'whoami']: history.append(cmd) list(history) # ['cd /tmp', 'cat file', 'pwd', 'ls -la', 'whoami'] # 'ls' було витіснено, коли прийшов 'whoami', бо maxlen=5 # Ковзне середнє window = deque(maxlen=3) for reading in [10, 20, 30, 40, 50]: window.append(reading) print(sum(window) / len(window)) # 10.0, 15.0, 20.0, 30.0, 40.0 ``` **namedtuple — легкий тип запису** ```python from collections import namedtuple Point = namedtuple('Point', ['x', 'y']) p = Point(3, 4) p.x # 3 — доступ за атрибутом p[0] # 3 — доступ за індексом (це все ще кортеж) p.x, p.y # 3, 4 x, y = p # розпакування теж працює ``` **Корисні методи namedtuple** ```python Point._fields # ('x', 'y') Point._make([3, 4]) # Point(x=3, y=4) з будь-якого ітерованого p._replace(x=10) # Point(x=10, y=4) — повертає новий екземпляр p._asdict() # {'x': 3, 'y': 4} ``` **namedtuple vs dict vs dataclass** ``` namedtuple — незмінний, сумісний з кортежем, дуже ефективний по пам'яті dict — змінний, гнучкі ключі, трохи більше пам'яті dataclass — змінний за замовчуванням, підтримує методи, type hints, __post_init__ ``` Якщо поля фіксовані й мутація не потрібна, `namedtuple` — найлегший вибір.

OrderedDict, ChainMap та вибір правильної колекції

#
**OrderedDict — словник, що запам'ятовує порядок вставки** У Python 3.7+ звичайний `dict` теж зберігає порядок вставки, тому `OrderedDict` рідко потрібний. Він корисний для методу `.move_to_end()` і коли хочеш явно позначити, що порядок важливий: ```python from collections import OrderedDict od = OrderedDict() od['a'] = 1 od['b'] = 2 od['c'] = 3 od.move_to_end('a') # перемістити 'a' в кінець list(od) # ['b', 'c', 'a'] od.move_to_end('c', last=False) # перемістити 'c' на початок list(od) # ['c', 'b', 'a'] # LRU-кеш (витіснення найдавніше використаного) class LRUCache: def __init__(self, capacity): self.cache = OrderedDict() self.cap = capacity def get(self, key): if key not in self.cache: return -1 self.cache.move_to_end(key) # позначити як нещодавно використаний return self.cache[key] def put(self, key, value): self.cache[key] = value self.cache.move_to_end(key) if len(self.cache) > self.cap: self.cache.popitem(last=False) # витіснити найстаріший ``` **Вибір правильної колекції** ``` Потреба Використовуй ──────────────────────────────────── ───────────────────── Підрахунок входжень Counter Групування, авто-ініціалізація ключів defaultdict(list) Накопичення без KeyError для нових ключів defaultdict(int/float) Швидка черга (обидва кінці) deque Ковзне вікно фіксованого розміру deque(maxlen=N) Легкий незмінний запис namedtuple Змінний запис з методами dataclass Словник з явним керуванням порядком OrderedDict Всe інше dict / list ``` **ChainMap — об'єднання кількох словників без копіювання** ```python from collections import ChainMap defaults = {'color': 'red', 'size': 'M'} overrides = {'color': 'blue'} merged = ChainMap(overrides, defaults) merged['color'] # 'blue' — знайдено в overrides спочатку merged['size'] # 'M' — передається до defaults # Записи йдуть до першого словника merged['weight'] = 'heavy' overrides # {'color': 'blue', 'weight': 'heavy'} ``` Корисний для шарування конфігурацій (налаштування користувача перевизначають дефолти) та для пошуку змінних за областями видимості.

Вправи:

01

#
Використайте `Counter`, щоб порахувати, скільки разів кожне слово з'являється в списку. Поверніть об'єкт Counter.
from collections import Counter

def word_count(words):
    # ваш код тут
    pass

words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
c = word_count(words)
print(c['apple'])   # 3
print(c['banana'])  # 2
print(c['grape'])   # 0 (Counter повертає 0 для відсутніх ключів)
Рішення 
from collections import Counter

def word_count(words):
    return Counter(words)
02

#
Поверніть 3 найпоширеніші слова в списку слів.
from collections import Counter

def top_three(words):
    # ваш код тут
    pass

words = ['the', 'cat', 'sat', 'on', 'the', 'mat', 'the', 'cat', 'is', 'fat']
print(top_three(words))  # [('the', 3), ('cat', 2), ('sat', 1)] або подібне
Рішення 
from collections import Counter

def top_three(words):
    return Counter(words).most_common(3)
03

#
Згрупуйте список слів за їх першою літерою за допомогою `defaultdict`. Поверніть словник, де кожен ключ — літера, а значення — список слів.
from collections import defaultdict

def group_by_letter(words):
    # ваш код тут
    pass

words = ['apple', 'banana', 'avocado', 'blueberry', 'cherry']
result = group_by_letter(words)
print(result['a'])  # ['apple', 'avocado']
print(result['b'])  # ['banana', 'blueberry']
Рішення 
from collections import defaultdict

def group_by_letter(words):
    groups = defaultdict(list)
    for word in words:
        groups[word[0]].append(word)
    return dict(groups)
04

#
Використайте `defaultdict(int)`, щоб підрахувати частоти літер у рядку. Поверніть defaultdict.
from collections import defaultdict

def letter_freq(s):
    # ваш код тут
    pass

freq = letter_freq('hello')
print(freq['l'])  # 2
print(freq['h'])  # 1
print(freq['z'])  # 0
Рішення 
from collections import defaultdict

def letter_freq(s):
    freq = defaultdict(int)
    for c in s:
        freq[c] += 1
    return freq
05

#
Використайте `OrderedDict` для створення кешу, що зберігає 3 останні унікальні доданих елементи (схоже на LRU). Реалізуйте методи `add(key, value)` і `get_all()`.
from collections import OrderedDict

class SmallCache:
    def __init__(self):
        self.cache = OrderedDict()
        self.max_size = 3

    def add(self, key, value):
        # ваш код тут
        pass

    def get_all(self):
        return list(self.cache.items())

c = SmallCache()
c.add('a', 1)
c.add('b', 2)
c.add('c', 3)
c.add('d', 4)  # 'a' має бути витіснений
print(c.get_all())  # [('b', 2), ('c', 3), ('d', 4)]
Рішення 
from collections import OrderedDict

class SmallCache:
    def __init__(self):
        self.cache = OrderedDict()
        self.max_size = 3

    def add(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.max_size:
            self.cache.popitem(last=False)  # видалити найстаріший

    def get_all(self):
        return list(self.cache.items())
06

#
Використайте `deque` для реалізації ковзного вікна максимуму: для списку чисел і розміру вікна k поверніть список максимального значення в кожному вікні.
from collections import deque

def sliding_max(nums, k):
    # ваш код тут
    pass

print(sliding_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]
Рішення 
from collections import deque

def sliding_max(nums, k):
    result = []
    window = deque()  # зберігає індекси
    for i, n in enumerate(nums):
        while window and nums[window[-1]] <= n:
            window.pop()
        window.append(i)
        if window[0] <= i - k:
            window.popleft()
        if i >= k - 1:
            result.append(nums[window[0]])
    return result
07

#
Використайте `namedtuple` для створення типу `Point` з полями `x` і `y`. Поверніть функцію, що обчислює відстань між двома точками.
from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])

def distance(p1, p2):
    # ваш код тут
    pass

a = Point(0, 0)
b = Point(3, 4)
print(distance(a, b))  # 5.0
Рішення 
from collections import namedtuple
import math

Point = namedtuple('Point', ['x', 'y'])

def distance(p1, p2):
    return math.sqrt((p2.x - p1.x) ** 2 + (p2.y - p1.y) ** 2)
08

#
Для двох Counter (частоти слів з двох текстів) поверніть новий Counter з об'єднаними частотами слів.
from collections import Counter

def combine_frequencies(c1, c2):
    # ваш код тут
    pass

c1 = Counter({'apple': 3, 'banana': 1})
c2 = Counter({'apple': 2, 'cherry': 4})
result = combine_frequencies(c1, c2)
print(result['apple'])   # 5
print(result['banana'])  # 1
print(result['cherry'])  # 4
Рішення 
from collections import Counter

def combine_frequencies(c1, c2):
    return c1 + c2
09

#
Використайте `deque` з `maxlen` для збереження лише останніх N елементів, доданих до потоку. Реалізуйте клас `StreamBuffer` з методами `push(item)` і `get_recent()`.
from collections import deque

class StreamBuffer:
    def __init__(self, maxlen):
        # ваш код тут
        pass

    def push(self, item):
        # ваш код тут
        pass

    def get_recent(self):
        return list(self.buffer)

buf = StreamBuffer(3)
for x in [1, 2, 3, 4, 5]:
    buf.push(x)
print(buf.get_recent())  # [3, 4, 5]
Рішення 
from collections import deque

class StreamBuffer:
    def __init__(self, maxlen):
        self.buffer = deque(maxlen=maxlen)

    def push(self, item):
        self.buffer.append(item)

    def get_recent(self):
        return list(self.buffer)
10

#
Для списку транзакцій (кожна — словник з 'category' і 'amount') використайте `defaultdict` для обчислення загальної суми за категорією.
from collections import defaultdict

def totals_by_category(transactions):
    # ваш код тут
    pass

txns = [
    {'category': 'food',    'amount': 12.5},
    {'category': 'travel',  'amount': 200.0},
    {'category': 'food',    'amount': 8.0},
    {'category': 'travel',  'amount': 50.0},
    {'category': 'books',   'amount': 25.0},
]
result = totals_by_category(txns)
print(result['food'])    # 20.5
print(result['travel'])  # 250.0
Рішення 
from collections import defaultdict

def totals_by_category(transactions):
    totals = defaultdict(float)
    for t in transactions:
        totals[t['category']] += t['amount']
    return dict(totals)