Какая структура данных у коллекций?

Структура данных Python коллекций

Python содержит несколько встроенных коллекций в модуле collections, каждая с уникальной внутренней структурой и характеристиками.

1. deque (двусторонняя очередь)

Структура: Двусвязный список

from collections import deque

q = deque([1, 2, 3])
q.appendleft(0)   # O(1) — добавление в начало!
q.append(4)       # O(1)
q.popleft()       # O(1) — удаление с начала!
q.pop()           # O(1)

# Внутренне:
# Блоки по 64 элемента, связанные указателями
# Позволяет быстрые операции с обеих сторон

Когда использовать:

• Очередь FIFO: q.append(), q.popleft()
• Стек LIFO: q.append(), q.pop()
• Буфер кольцевой (с maxlen):

last_events = deque(maxlen=100)  # Только последние 100
for event in stream():
    last_events.append(event)  # Старые автоматически удаляются

2. Counter (счётчик)

Структура: dict с оптимизацией для подсчёта

from collections import Counter

fruits = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
c = Counter(fruits)
print(c)  # Counter({'apple': 3, 'banana': 2, 'cherry': 1})

# Это по сути dict
print(c['apple'])      # 3
print(c.most_common(2))  # [('apple', 3), ('banana', 2)]

# Теоретически O(n), но очень быстро на практике
c.update(['apple'])    # Инкрементирует счётчик

Когда использовать:

• Подсчёт частоты элементов
• Top K задачи
• Анализ текста

text = "hello world hello"
word_freq = Counter(text.split())
print(word_freq.most_common(1))  # ('hello', 2)

3. defaultdict

Структура: dict с дополнительной функцией default_factory

from collections import defaultdict

# Обычный dict требует проверки ключа
regular_dict = {}
if 'users' not in regular_dict:
    regular_dict['users'] = []
regular_dict['users'].append('John')

# defaultdict автоматически создаёт значение
dd = defaultdict(list)  # default_factory = list
dd['users'].append('John')  # Автоматически создаст пустой list

# Работает как dict, но с O(1) поиском
dd['posts'].append('First post')  # 'posts' создаётся если не существует

Примеры:

# Группировка данных
from collections import defaultdict

students_by_grade = defaultdict(list)
for name, grade in [('Alice', 'A'), ('Bob', 'B'), ('Charlie', 'A')]:
    students_by_grade[grade].append(name)

print(students_by_grade['A'])  # ['Alice', 'Charlie']

# Подсчёт с дефолтом
word_count = defaultdict(int)
for word in 'hello world hello'.split():
    word_count[word] += 1

4. OrderedDict

Структура: dict + двусвязный список для сохранения порядка

from collections import OrderedDict

# Python 3.7+ — обычный dict тоже сохраняет порядок
# Но OrderedDict имеет дополнительные методы

od = OrderedDict([('a', 1), ('b', 2), ('c', 3)])

# Сохраняет порядок вставки
for key, value in od.items():
    print(key, value)  # a 1, b 2, c 3

# Дополнительные методы
od.move_to_end('a')     # Перемещает в конец
od.popitem(last=False)  # Удаляет первый элемент

Когда использовать:

• Сохранение порядка вставки (но Python 3.7+ dict это делает)
• move_to_end() для LRU кэша

5. namedtuple

Структура: Неизменяемый класс (кортеж с именованными полями)

from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])
p = Point(10, 20)

print(p.x)      # 10 (доступ как атрибут)
print(p[0])     # 10 (доступ как кортеж)
print(len(p))   # 2

# Это кортеж! Неизменяемый
# p.x = 15  # AttributeError

# Быстрее чем обычный класс
for _ in range(1_000_000):
    p = Point(10, 20)  # Быстро

Когда использовать:

• Упаковка нескольких значений
• Возврат нескольких значений из функции
• Ключи dict (неизменяемость критична)

from collections import namedtuple

User = namedtuple('User', ['id', 'name', 'email'])

def get_user():
    return User(123, 'John', 'john@example.com')

user = get_user()
print(user.name)  # 'John'

# Используем как ключ (неизменяемый)
user_data = {user: 'some_data'}  # OK

6. ChainMap

Структура: Группа словарей, просматриваемых в порядке приоритета

from collections import ChainMap

defaults = {'color': 'red', 'size': 'medium'}
config = {'color': 'blue'}

cm = ChainMap(config, defaults)
print(cm['color'])  # 'blue' (из config)
print(cm['size'])   # 'medium' (из defaults)

# Изменение через ChainMap меняет первый dict
cm['color'] = 'green'
print(config)  # {'color': 'green'}
print(defaults)  # не изменился

Когда использовать:

• Слои конфигурации (CLI args → config file → defaults)
• Области видимости переменных

Сложность операций

*в начале/конце

Итоговая таблица использования

# Очередь FIFO
from collections import deque
queue = deque()
queue.append(item)      # Добавить в конец
item = queue.popleft()  # Извлечь из начала

# Частотный анализ
from collections import Counter
freq = Counter(items)
freq.most_common(10)  # Топ 10

# Dict с дефолтными значениями
from collections import defaultdict
dd = defaultdict(list)  # или int, set, etc

# Кортеж с именами
from collections import namedtuple
Point = namedtuple('Point', 'x y')

# Многоуровневые настройки
from collections import ChainMap
config = ChainMap(user_config, default_config)