5.02. Алгоритмы и структуры
Алгоритмы и структуры
При первом знакомстве с Python новички часто сталкиваются с парадоксом: язык позиционируется как простой, интуитивный и высокого уровня, однако в подавляющем большинстве курсов, учебников и собеседований сразу после базового синтаксиса начинается изучение структур данных и алгоритмов. Это не случайность. Дело в том, что независимо от языка программирования, эффективное решение задач требует понимания двух фундаментальных компонентов: как организованы данные и как обрабатываются.
Python, несмотря на свою абстракцию, не является исключением. Напротив, именно его гибкость и богатство стандартной библиотеки делают понимание внутреннего устройства структур данных критически важным. Вы можете написать рабочий код, используя list, dict или set, не зная их устройство — но выбор неоптимальной структуры приведёт к неэффективному использованию памяти, замедлению выполнения и труднообнаружимым ошибкам в масштабируемых системах.
Вы можете решать задачи, не углубляясь в структуры данных и алгоритмы. Но рано или поздно столкнётесь с вопросами: Почему мой скрипт тормозит при обработке 100 тыс. записей? Как эффективно обрабатывать вложенные JSON-структуры? Почему при работе с графиками возникает переполнение стека? Ответы на эти вопросы лежат в понимании того, как устроены данные и какие операции над ними эффективны. Python скрывает сложность, но не отменяет законы информатики. Выбор структуры данных влияет на сложность алгоритма, потребление памяти и масштабируемость системы. Представим, что мы пришли в библиотеку, где много книг, но они разложены по алфавиту, темам и авторам. Это нужно для того, чтобы мы могли быстро найти книгу. А если всё хаотично бросить в одну кучу, то пришлось бы перебирать каждую, и это долго. В программировании всё аналогично, но вместо книг - данные - числа, тексты, списки, заказы и так далее.
Структуры данных — это способы раскладывать данные, чтобы их было удобно хранить и быстро находить.
Алгоритмы — это инструкции, как что-то делать с этими данными: найти, отсортировать, изменить, сравнить.
Структура данных — это способ организации, хранения и управления данными, определяющий доступ к элементам, порядок их следования и операции, которые можно над ними выполнять. В Python многие структуры реализованы как встроенные типы или доступны через стандартные модули (collections, heapq, array и др.). Однако важно понимать, что за каждой из них стоит конкретная модель поведения и временная сложность операций.
К примеру, у нас есть список дел - купить хлеб, позвонить маме, сделать домашнее задание. Как мы храним список? В блокноте, телефоне или голове. В программе тоже надо такой список где-то хранить, и Python предлагает несколько вариантов:
- list — как обычный список
- dict — как словарь (например, «имя» → «телефон»)
- set — как корзина уникальных вещей (без повторов)
Каждый из этих способов — структура данных. И каждая хороша для своих задач.
list напоминает журнал, в котором каждая запись имеет номер.
Если мы спросим «Кто под номером 2», то получим, допустим студента с именем «Тимур». Это доступ по номеру (индексу).
Добавить нового ученика в конец — легко. Но если захочется вставить кого-то между Борисом и Викой, придётся всех после него «подвинуть» — это вставка в середину.
Индекс — это номер элемента в списке. В Python нумерация с нуля: первый элемент — list[0], второй — list[1].
А теперь представим себе очередь, где каждый человек помнит, кто следующий. Анна знает, что после неё — Борис. Борис знает, что после него — Вика. Вика — никого. Чтобы найти Вику, нужно пройти от Анны → к Борису → к Вике. Это обход от начала.
Но зато, если мы хотим поставить Диму между Борисом и Викой — просто говорим Борису: «Теперь после тебя — Дима», а Диме — «После тебя — Вика». Никого не нужно «переставлять».
Узел — это один элемент в такой цепочке. У него есть данные (имя, медкарта), и ссылка на следующего (и возможно, на предыдущего). Такой список называется связанным, потому что элементы связаны ссылками, а не стоят впритык.
Связанный список — это набор узлов, каждый из которых содержит данные и ссылку на следующий (в односвязном) или следующий и предыдущий (в двусвязном) узел. В Python нет встроенной реализации, но её легко создать с помощью классов.
Вставка и удаление в произвольной позиции — O(1), если известен узел. Доступ по индексу — O(n), так как требуется обход от начала. Не требует перераспределения памяти при росте, но расходует дополнительную память на указатели.
Встроенный тип list в Python не является связанным списком, а реализован как динамический массив (обычно называемый vector в других языках).
Теперь представим шкаф, где есть 10 одинаковых ящиков, стоящих друг за другом, и в каждом - одна вещь. Мы знаем, что хлеб в ящике №5, и чтобы взять его, сразу идём к пятому ящику. Это быстрый доступ по индексу (номеру) - O(1).
Но если захочется вставить что-то в третий ящик, и он уже занят — придётся вытащить всё, что справа, передвинуть на один вправо, и только потом вставить новое. Это медленно — O(n).
Однородность типа — значит, в массиве все элементы одного вида: только числа, только буквы и т.п. Это позволяет хранить их плотно, экономя память.
Смежное размещение — все ячейки идут подряд в памяти, как соседние квартиры в доме.
Как раз-таки шкаф с ящиками - это массив.
Массив — это непрерывный блок памяти, содержащий элементы одного типа, доступ к которым осуществляется по индексу за время O(1). В Python встроенного массива фиксированного типа нет, но модуль array предоставляет тип array.array, который хранит числовые данные компактно. Более широкое применение находят NumPy-массивы (numpy.ndarray), особенно в научных расчётах.
Производительность достигается за счёт однородности типа и смежного размещения. Вставка/удаление в середине — O(n), так как требуется сдвиг всех последующих элементов.
Теперь представим шкафчик, и его номер мы не помним, но у нас есть ключ, например слово «Петров». Система берёт это слово, делает из него число (например: П=16, е=5, т=20… и считает формулу) — это хеш-функция. Получается номер шкафчика: 42.
Мы кладём вещи в 42-й шкафчик, а потом, когда приходим, снова говорим «Петров», и система снова считает хеш — и ведёт к 42.
Но если двое людей получили один и тот же номер (например, «Петров» и «Сидоров» дали хеш 42) — это коллизия.
Хеш-таблица — это структура, обеспечивающая среднюю сложность доступа, вставки и удаления O(1) за счёт преобразования ключа в индекс массива с помощью хеш-функции. В Python основные реализации:
- dict — хеш-таблица с неупорядоченными (до Python 3.7) и упорядоченными (с 3.7+) парами ключ-значение.
- set — хеш-таблица без значений, только ключи.
При коллизиях (совпадении хешей) используется метод цепочек (chaining) или открытая адресация (в CPython применяется модифицированная открытая адресация). При заполнении таблица автоматически увеличивается (resize), что вызывает временное замедление.
Собственно, метод цепочек подразумевает, что в ячейке 42 висит список «Петров - Сидоров», и придётся проверить по одному.
А открытая адресация говорит, что если 42 занят — попробовать 43, потом 44 и т.д.
Порядок в dict теперь сохраняется, но это побочный эффект реализации, а не часть API до версии 3.7+. Хеш-функция должна быть детерминированной и равномерно распределять ключи. Объекты, используемые в качестве ключей, должны быть хешируемыми (иметь метод __hash__() и быть неизменяемыми).
Производительность dict и set зависит от качества хеш-функции и коэффициента заполнения. В реальных системах плохие хеш-функции могут привести к атакам типа hash flooding.
Вернёмся к очередям. В больнице есть очередь людей, но представьте, что обслуживать будут по степени болезни. То есть, не кто первый пришёл, а кто самый больной. Допустим, пациента осматривают, дают приоритет (от 1 до 10 например), и всегда берут того, у кого приоритет самый высокий (или самый низкий, зависит от типа кучи). В Python heapq — это мин-куча: всегда извлекается наименьший элемент.
Куча — это специализированное деревообразное представление данных, удовлетворяющее свойству кучи: значение родителя либо не меньше (max-heap), либо не больше (min-heap), чем значения потомков. Наиболее распространена min-куча, где минимальный элемент всегда находится в корне.
В Python куча реализована в модуле heapq, который работает с обычными списками, интерпретируя их как бинарные мин-кучи. Операции - вставка O(log n), извлечение O(log n) и получение минимума O(1). Применяется для очередей с приоритетом и в алгоритмах.
heapq не предоставляет отдельный тип, а набор функций, работающих с list'ом. Это позволяет использовать кучу как часть других структур, но требует аккуратности при модификации списка вручную.
А теперь представьте очередь, где первым будет обслуживаться тот, кто зашел последним. Странно, не так ли? Это стек. LIFO = Last In, First Out.
Стек — структура данных с дисциплиной LIFO (Last In, First Out): последний добавленный элемент извлекается первым. Основные операции: push (добавить), pop (извлечь), peek (посмотреть вершину).
В Python list может использоваться как стек:
stack = []
stack.append(item) # push
item = stack.pop() # pop
Использование insert(0, item) или pop(0) превращает list в неэффективную очередь — O(n).
И конечно есть классическая очередь, как в жизни, кто первым пришел, тот первым ушёл.
Очередь — FIFO (First In, First Out). Первый добавленный элемент извлекается первым. Встроенный list неэффективен для очередей, так как удаление из начала — O(n). Вместо этого используют:
- collections.deque — двусторонняя очередь на основе связанного списка, поддерживающая O(1) вставку и удаление с обоих концов.
- queue.Queue — потокобезопасная очередь, полезная в многопоточных приложениях.
from collections import deque
q = deque()
q.append(item) # enqueue
item = q.popleft() # dequeue
У каждого человека есть родители, дети. А в программировании дерево - является структурой по аналогии с генеалогическим древом, где есть один корень (прадед), у него есть дети (деды), у которых есть внуки, и так далее.
Дерево — иерархическая структура, состоящая из узлов, где один узел является корнем, а остальные разделены на непересекающиеся поддеревья. Наиболее распространённые виды:
- Бинарное дерево — каждый узел имеет не более двух потомков.
- Бинарное дерево поиска (BST) — левое поддерево содержит ключи меньше корня, правое — больше.
- Сбалансированные деревья (например, AVL, красно-чёрные) — гарантируют высоту
O(log n), обеспечивая эффективный поиск.
В Python деревья не встроены, но легко реализуются через классы:
class TreeNode:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
Поиск в BST — O(log n) в среднем, O(n) в худшем случае (при вырождении в список). Обходы: in-order, pre-order, post-order, level-order — фундаментальные паттерны рекурсивной обработки. Применение: парсеры выражений, файловые системы, базы данных, алгоритмы машинного обучения (решающие деревья).
Алгоритм — чётко определённая последовательность действий для решения задачи за конечное число шагов. В отличие от структур данных, алгоритмы описывают процесс, а не форму хранения.
К примеру, у нас есть список ["Вася", "Анна", "Борис"], и мы хотим ["Анна", "Борис", "Вася"]. Python умеет: сортировать:
sorted(["Вася", "Анна", "Борис"]) # → ['Анна', 'Борис', 'Вася']
Сортировка — упорядочивание элементов по заданному критерию. Python предоставляет встроенные функции:
- sorted(iterable) — возвращает новый отсортированный список.
- list.sort() — сортирует на месте.
Оба используют алгоритм Timsort — гибридный, стабильный алгоритм, сочетающий сортировку слиянием и сортировку вставками. Он оптимизирован для реальных данных, включая частично упорядоченные последовательности. Timsort сохраняет относительный порядок равных элементов (стабильность), что критично в некоторых приложениях.
Поиск — нахождение элемента в структуре данных.
Линейный поиск проходит по всем элементам последовательно. Сложность: O(n). Применим к любым итерируемым объектам, даже неупорядоченным.
Бинарный поиск работает только на отсортированных массивах. На каждом шаге сужает диапазон поиска вдвое. Сложность: O(log n)
Вот мы перебираем один элемент за другим. Если у нас 1000 имён, может понадобится 1000 шагов - это линейный поиск. А если же список отсортирован, то открываем посередине и ориентируемся - «Борис» — а тебе нужен «Вася»? Значит, ищи справа.
В Python нет встроенной функции бинарного поиска, но она доступна в модуле bisect:
import bisect
index = bisect.bisect_left(sorted_list, target)
bisect позволяет эффективно вставлять элементы в отсортированный список с сохранением порядка.
Рекурсия — подход, при котором функция вызывает саму себя для решения подзадач меньшего размера. Фундаментальна для работы с древовидными структурами, разбором выражений, алгоритмами «разделяй и властвуй». Пример: факториал
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
Глубина рекурсии ограничена (по умолчанию ~1000), чтобы предотвратить переполнение стека вызовов. Можно изменить через sys.setrecursionlimit(), но это опасно. Рекурсивные алгоритмы часто менее эффективны по памяти, чем итеративные, из-за накладных расходов на стек вызовов.
Хвостовая рекурсия не оптимизируется в Python (в отличие от функциональных языков). Для глубоких деревьев рекомендуется итеративный обход с явным стеком.
Если вас смутило Большое О, то это способ измерить, как растёт время работы программы при увеличении данных.
Пример:
O(1)— всегда одинаковое время, как бы ни был большой список. Например: взять первый элемент.O(n)— время растёт прямо пропорционально размеру. Если список в 10 раз длиннее — в 10 раз дольше искать.O(log n)— очень медленный рост. Удвой список — добавь один шаг. Это бинарный поиск.O(n²)— очень медленно. Для 1000 элементов — миллион операций.