Привет, Хабр!

Если вы хоть раз пытались вкатиться в алгоритмы, решали задачки на LeetCode или готовились к собеседованиям, то наверняка ловили в лицо обидную ошибку Time Limit Exceeded (TLE). Вроде бы логика решения идеальная, на базовых тестах всё работает, но при отправке код отваливается по времени.

Самая классическая причина такой боли у новичков — банальное list.pop(0).

Когда вы пишете эту строчку, чтобы достать первый элемент из очереди, Python не просто забирает значение. Обычный список под капотом — это динамический массив. Удалив первый элемент, язык вынужден сдвинуть все оставшиеся элементы на одну позицию влево. Если в списке миллион элементов, это миллион операций ради одного удаления. Итог: скрытая сложность там, где вы ожидали быстрый ответ, и проваленный тест.

Как это лечить? Перестать использовать стандартные структуры данных там, где они не справляются, и вспомнить про встроенный модуль collections.

Вам не нужно писать pip install — это стандартная библиотека Python, которая поставляется из коробки. Разработчики языка уже написали оптимизированные структуры на C, чтобы вы могли эффективно работать с очередями, подсчетами и сложными словарями, не просаживаясь по производительности.

Небольшое лирическое отступление: если вы хотите увереннее писать код на Питоне, понимать, как все устроено под капотом, и просто прокачать базу — заглядывайте на мой авторский и полностью бесплатный курс «ООП Python: Часть 1» на Stepik.

Ну а теперь — погнали разбираться с collections!

2. deque: Двусторонняя очередь (Ваш лучший друг для BFS)

Теория: Стек, очередь Представьте обычную очередь в кассу супермаркета: кто первый пришел, тот первый и ушел. Это принцип FIFO (First In, First Out). А теперь представьте стопку тарелок на кухне: вы берете верхнюю тарелку, которую положили последней. Это стек — LIFO (Last In, First Out).

Обычный питоновский list — это идеальный стек. Вызовы .append() и .pop() работают с концом списка мгновенно. Но как только мы пытаемся сделать из него очередь и пишем .pop(0), всё ломается по производительности.

Тут на сцену выходит deque (Double-Ended Queue, читается как «дек»). Это структура, которая берет лучшее от обоих. Вы можете добавлять и забирать элементы с любого конца абсолютно безболезненно.

Почему это так быстро? Почему list.pop(0) — это сложность ? Потому что питоновский список — это динамический массив. Удаление первого элемента оставляет дыру в памяти, и Питон вынужден физически сдвинуть все оставшиеся элементы на шаг влево.

А вот deque под капотом реализован (упрощенно) как двусвязный список. Элементы не лежат в памяти сплошным куском, а просто ссылаются друг на друга: «я знаю, кто за мной, и знаю, кто передо мной». Поэтому для добавления или удаления элемента слева (.appendleft(), .popleft()) Питону нужно просто переписать пару ссылок. Никаких сдвигов. Чистая сложность .

Где применять в алгоритмах:

1. Поиск в ширину (BFS): Абсолютный мастхэв для обхода деревьев и графов по уровням. Если в задаче нужно найти кратчайший путь в лабиринте не взвешенного графа — рука сама должна тянуться к from collections import deque.

2. Скользящее окно (Sliding Window): Особенно в задачах вроде Sliding Window Maximum (хард на LeetCode), где мы храним в деке индексы кандидатов на максимум и легко отбрасываем устаревшие элементы с одного конца, а новые добавляем с другого.

Пример из жизни: Медленный vs Быстрый BFS Давайте напишем простейший обход графа в ширину. Допустим, мы ищем выход из лабиринта.

❌ Как пишет новичок (и получает TLE на больших графах):

def bad_bfs(graph, start_node):
    queue = [start_node] # Используем обычный список
    visited = set([start_node])
    
    while queue:
        # Ужасно! Сдвигает весь массив влево, O(n) на каждой итерации
        node = queue.pop(0) 
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

✅ Как пишет профи (Быстро и чисто):

from collections import deque

def good_bfs(graph, start_node):
    queue = deque([start_node]) # Инициализируем дек
    visited = set([start_node])
    
    while queue:
        # Красота! Мгновенное удаление за O(1)
        node = queue.popleft() 
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Разница всего в двух строчках (deque и .popleft()), но на графе со 100 000 вершин первый код может работать секунды, а второй отработает за миллисекунды.

3. Counter: Математика над словарями

Теория: Зачем считать вручную? Признайтесь, каждый из нас писал этот код. Вы идете по массиву или строке и считаете, сколько раз встречается каждый элемент.

# Классическая боль новичка
counts = {}
for char in s:
    if char in counts:
        counts[char] += 1
    else:
        counts[char] = 1

Или, если вы уже выучили пару трюков: counts[char] = counts.get(char, 0) + 1.

Забудьте. Для этого есть Counter. По сути, это умный подкласс обычного питоновского словаря (dict), который создан ровно для одной задачи — считать объекты. Вы просто скармливаете ему любой итерируемый объект (список, кортеж, строку), и он сам собирает частотный словарь, написанный на быстром C.

Фичи, о которых не все знают: Помимо того, что Counter избавляет от написания лишних циклов, у него есть настоящие суперсилы:

1. Метод .most_common(k): Возвращает список из самых частых элементов в формате [(элемент, количество), ...]. Если на собеседовании просят решить задачу “Top K Frequent Elements” — вы уже знаете, какой метод использовать для подсчета базовой статистики.

2. Арифметика: Это самое вкусное. Счетчики можно складывать (+), вычитать (-), пересекать (& — оставляет минимальные общие значения) и объединять (| — оставляет максимальные). Это звучит как магия, но невероятно выручает при сравнении массивов данных.

Где применять в алгоритмах:

• Проверка строк на анаграммы: Идеально подходит для сравнения составов двух строк или массивов.

• Частотный анализ: Любые задачи в духе «найдите элемент, который встречается больше раз» (Majority Element).

• Поиск уникальных элементов: Задача «Найти первый неповторяющийся символ в строке» решается в два счета. Создали Counter, прошлись по исходной строке, вернули первый символ со значением 1.

Пример из жизни: Valid Anagram Популярная задача с LeetCode: даны две строки s и t. Нужно вернуть True, если t является анаграммой s (состоит из тех же букв в том же количестве).

❌ Решение в лоб: Сортировка обеих строк и их сравнение — return sorted(s) == sorted(t). Коротко, но сортировка занимает времени. На длинных строках это медленно.

✅ Решение с Counter: Линейное время по скорости и красота в коде.

from collections import Counter

def is_anagram(s: str, t: str) -> bool:
    # Просто сравниваем два частотных словаря
    return Counter(s) == Counter(t)

А вот вам бонусный трюк с вычитанием. Задача “Ransom Note”: можно ли составить письмо ransomNote из букв, вырезанных из журнала magazine?

def can_construct(ransomNote: str, magazine: str) -> bool:
    # Вычитаем из букв письма буквы журнала. 
    # Если в итоге счетчик пуст — значит, букв журнала хватило на всё письмо!
    return len(Counter(ransomNote) - Counter(magazine)) == 0

4. defaultdict: Забываем про KeyError навсегда

Теория: Боль обычных словарей Любой питонист рано или поздно сталкивается с KeyError. Это происходит, когда вы пытаетесь обратиться к ключу словаря, которого там еще нет.

В алгоритмических задачах мы постоянно собираем данные в словари: группируем элементы, строим графы, сохраняем промежуточные результаты. И каждый раз приходится писать раздражающий защитный код:

# Классическая рутина
if key not in my_dict:
    my_dict[key] = []
my_dict[key].append(value)

Да, можно использовать метод .setdefault(), но код все равно выглядит перегруженным. defaultdict решает эту проблему радикально. При его создании вы передаете функцию-фабрику (например, list, int, set). Если вы обращаетесь к несуществующему ключу, defaultdict автоматически вызывает эту фабрику, создает дефолтное значение и кладет его по этому ключу. Никаких проверок, никаких KeyError.

Где применять в алгоритмах:

• Построение графов (списки смежности): Это абсолютный топ-1 юзкейс. Графы в задачах часто задаются массивом ребер, и переводить их в удобный словарь нужно постоянно.

• Группировка данных: Когда нужно раскидать элементы массива по корзинам (например, сгруппировать слова по их длине или отсортировать анаграммы).

• Сложные вложенные структуры: Когда вам нужен словарь, внутри которого лежат другие словари или множества.

Пример из жизни: Строим граф Представьте стандартную задачу на графы. Вам на вход дают массив ребер edges = [[0, 1], [0, 2], [1, 2], [2, 3]]. Это неориентированный граф. Нам нужно построить список смежности — словарь, где ключ — это узел, а значение — список всех его соседей.

❌ Как это выглядит на обычных словарях (громоздко и шумно):

edges = [[0, 1], [0, 2], [1, 2], [2, 3]]
graph = {}

for u, v in edges:
    # Защищаемся от KeyError для узла u
    if u not in graph:
        graph[u] = []
    # Защищаемся от KeyError для узла v
    if v not in graph:
        graph[v] = []
        
    graph[u].append(v)
    graph[v].append(u)

✅ Элегантное решение с defaultdict:

from collections import defaultdict

edges = [[0, 1], [0, 2], [1, 2], [2, 3]]
# Говорим: "Если ключа нет, создай пустой список"
graph = defaultdict(list)

for u, v in edges:
    # Никаких проверок! Просто добавляем соседей
    graph[u].append(v)
    graph[v].append(u)

Код сократился в два раза, читать его стало намного приятнее, а вероятность опечататься или забыть проверку ключа свелась к нулю.

Точно так же это работает с числами. Если вам нужно что-то инкрементировать, но вы не хотите использовать Counter (например, если логика сложнее обычного подсчета), используйте defaultdict(int). При обращении к пустому ключу он вернет 0, и вы сможете смело писать my_dict[key] += 1. А для хранения уникальных элементов на лету идеально подойдет defaultdict(set).

5. Бонус: Краткий обзор других полезных классов

Если deque, Counter и defaultdict — это ваша тяжелая артиллерия, то эти два класса — отличные инструменты для тонкой настройки кода, которые покажут интервьюеру вашу инженерную культуру.

namedtuple: Читаемость превыше всего В сложных задачах на графы (особенно при поиске кратчайшего пути с препятствиями) мы часто кладем в очередь не просто одно значение, а целое состояние: координаты, текущую длину пути, флаг наличия ключа.

Обычно это делают через кортежи: queue.append((0, 0, 1, False)). А потом при извлечении начинается ад с индексами: x, y = node[0], node[1], или еще хуже — вы пытаетесь вспомнить, что значит node[3] через сотню строк кода.

namedtuple решает это изящно и без накладных расходов по памяти (под капотом это все тот же неизменяемый кортеж).

from collections import namedtuple

# Создаем шаблон состояния
State = namedtuple('State', ['x', 'y', 'distance', 'has_key'])

# Инициализируем
current_node = State(x=5, y=10, distance=3, has_key=True)

# Обращаемся по-человечески
print(current_node.distance) # Выведет: 3

Ваш код становится самодокументируемым. Читать его — одно удовольствие.

OrderedDict: Жив ли он после Python 3.7? Многие знают, что начиная с версии Python 3.7 обычные словари (dict) научились сохранять порядок вставки ключей. Кажется, что OrderedDict должен был уйти на пенсию.

Но у него осталась одна фича, ради которой его до сих пор используют: метод .move_to_end(key).

На собеседованиях в FAANG и другие крупные компании обожают давать задачу LRU Cache (кэш, который вытесняет наименее используемые элементы). Реализовать её с нуля на связных списках — та еще боль. А с OrderedDict это делается в пару строк: при каждом обращении к элементу вы просто перекидываете его в конец словаря вызовом cache.move_to_end(key). Тот элемент, который застрял в самом начале словаря (на позиции 0), автоматически становится кандидатом на удаление.

from collections import OrderedDict

cache = OrderedDict()
cache['a'] = 1
cache['b'] = 2

# Имитируем обращение к элементу 'a'
cache.move_to_end('a') 

# Теперь 'b' стоит первым в очереди на удаление, так как 'a' мы "обновили"
oldest_key = next(iter(cache))
print(f"Кандидат на вытеснение: {oldest_key}") # Выведет: Кандидат на вытеснение: b

6. Шпаргалка по сложности (Big-O)

На алгоритмических секциях мало написать рабочий код — вас обязательно попросят оценить его временную сложность. И именно здесь правильный выбор структуры данных отделяет кандидата уровня Junior от крепкого Middle.

(Кстати, если вы всё ещё плаваете в оценках сложности, путаетесь в логарифмах и не понимаете, откуда берется квадратичное время — очень советую сделать паузу и прочитать мою статью Понять Big O раз и навсегда. Она расставит всё по полочкам).

А для тех, кто уже в теме, я собрал краткую выжимку. Эту таблицу полезно просто держать в голове:

Как видите, collections — это не просто «синтаксический сахар» для красоты кода. В случае с очередями и поиском самых частых элементов это реальная алгоритмическая оптимизация, которая спасет ваш код от ошибки Time Limit Exceeded.

7. Заключение: Ваш новый алгоритмический арсенал

Стандартные списки и словари — это отличный инструмент на каждый день. Но когда дело доходит до оптимизации на собеседованиях или решения лимитных задач на LeetCode, их базового функционала часто не хватает.

Модуль collections — это легальный чит-код, который уже лежит в коробке с Python. Выбирая deque для очередей, Counter для аналитики и defaultdict для графов, вы убиваете сразу трех зайцев:

1. Спасаете код от TLE, используя структуры, написанные на быстром C и заточенные под конкретные задачи.

2. Пишете меньше кода, избавляясь от рутинных проверок и лишних циклов.

3. Показываете класс, давая понять интервьюеру, что вы не просто умеете переводить мысли в код, но и глубоко знаете стандартную библиотеку языка.

Анонсы новых статей, полезные материалы, а так же если в процессе у вас возникнут сложности, обсудить их или задать вопрос по этой статье можно в моём Telegram-сообществе. Смело заходите, если что-то пойдет не так, — постараемся разобраться вместе.

Пора закрепить на практике

Читать статьи полезно, но паттерны запоминаются только через руки. Если вы хотите прочувствовать всю мощь этих структур прямо сейчас, вот вам небольшая разминка на вечер (задачки легко ищутся на LeetCode):

• Для Counter: Задача 242. Valid Anagram. Попробуйте написать решение ровно в одну строчку.

• Для defaultdict: Задача 49. Group Anagrams. Сгруппируйте массив слов по анаграммам, не используя ни одного if для проверки наличия ключа.

• Для deque: Задача 200. Number of Islands. Идеальный полигон, чтобы написать свой первый чистый BFS без списка-очереди.

Удачи на собеседованиях и зеленых вам тестов!