Алгоритмические инструменты

Содержание и основные понятия

Не заменяй понимание названиями модулей. Сначала назови инвариант и сложность, затем выбери
deque
,
Counter
, кучу или двоичный поиск.
структуры данных
10-11 класс
ЕГЭ: идеи алгоритмов
01
collections: данные по смыслу
Counter(iterable)
Частотный словарь: считает появление значений.
Похоже на
dict
, но выражает намерение.
deque()
Очередь с быстрым
appendleft
и
popleft
.
Не удаляй начало обычного списка много раз.
defaultdict(list)
Создает значение по умолчанию для нового ключа.
Удобно при группировке, но обычный
dict.get
иногда проще.
namedtuple / dataclass
Дают именованные поля записи.
Для учебной пары часто достаточно обычного кортежа.
02
Поток, выбор и поиск
Инструмент
Задача
Не использовать вместо
itertools.combinations
Перебрать все пары или наборы малого размера.
Линейного алгоритма на больших данных.
functools.lru_cache
Запомнить результаты чистой рекурсивной функции.
Объяснения рекурсии, если кеш скрывает важное состояние.
heapq
Многократно брать минимум или хранить top-k.
Полной сортировки, если нужен весь порядок один раз.
bisect
Найти позицию в уже отсортированном списке.
Поиска в неотсортированных данных.
Инвариант кучи
heapq
гарантирует минимум в позиции
0
. Остальной список не отсортирован полностью: не обращайся с кучей как с готовым отсортированным массивом.
03
Пример: три лучших результата
Если требуется только несколько максимальных значений,
heapq.nlargest
точно описывает задачу. Когда нужен полностью отсортированный результат, выбирай
sorted
.
import
heapq
scores = [72, 91, 84, 68, 95, 88]
leaders = heapq.nlargest(3, scores)
print(leaders)
Результат
[95, 91, 88]
содержит только нужную тройку. Исходный список при этом не изменяется.
04
Быстрая проверка
Какой контейнер уместнее для многократного извлечения элементов с начала очереди?