Чтение кода для анализа темпов роста
Проверка кода на корректность vs проверка кода на сложность
Проверка кода на корректность ловит логические ошибки: неправильные условия, ошибки на единицу в индексах, пропущенные проверки на null. Проверка кода с учётом сложности ловит другой класс дефектов: код, который работает корректно при N = 100, но растёт катастрофически при N = 100 000.
Этот урок связан с более глубоким расследованием в курсе unhamming: Недостающая глава: алгоритмическая сложность охватывает Big O в контексте рабочих дефектов, & MOAD-0001: осадочный дефект отображает паттерн на 60+ экосистемах программного обеспечения.
Два эвристических подхода для проверки
Вложенные циклы умножают сложность. Два вложенных цикла по N элементов производят O(N²). Три производят O(N³). При проверке: сначала подсчитайте глубину вложения циклов.
Последовательный контейнер внутри горячего цикла. Любая проверка .contains(), .includes(), .find(), или in list внутри цикла стоит O(N) на проверку. На N итерациях: O(N²) в сумме. Этот паттерн появляется в рабочем коде на десятках экосистем — GHC Haskell компилятор, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. Одна и та же ошибка, разные кодовые базы.
Проверка: find_duplicates
Проверьте следующую функцию Python на сложность:
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001: осадочный дефект
Один и тот же дефект, шестьдесят экосистем
Паттерн if x not in list: list.append(x) внутри цикла появляется — и появлялся — в рабочем коде на десятках экосистем программного обеспечения:
- GHC (Haskell компилятор): решатель зависимостей, O(N²) при N = 50 000 пакетов, сборки в 17 минут
- Python pip: разрешение конфликтов зависимостей
- Apache Maven: дедупликация пути класса
- Rust Cargo: объединение функций
- TypeScript компилятор: разрешение модулей
- Godot / Redot игровой движок: обход графа узлов
Ни одна из этих команд не допустила ошибку. Они написали правильный код при малых N. N вырос. Код затвердел. Паттерн имеет имя: MOAD-0001, осадочный дефект. Осадок: правильный, безвредный в тонких слоях. Со временем слои накапливаются и затвердевают.
Исправление
В каждом случае: замените последовательный контейнер на хеш-контейнер. Одна строка. Нулевое изменение поведения при корректных входах. Ускорение в 100–1 000 раз при реальных N.
Исправление работает, потому что две операции должны оставаться быстрыми:
1. Проверка членства: был ли этот элемент видён раньше?
2. Упорядоченный вывод: вернуть элементы в порядке их появления (иногда требуется, иногда нет).
Множество обрабатывает (1) в O(1). Если (2) также важна, держите отдельный список для упорядоченного вывода и множество для проверки членства. Две структуры данных, каждая делает одну работу.
Ответ рецензенту
Запрос на слияние исправляет MOAD-0001 в функции обхода графа проекта. Рецензент комментирует:
> "Множества не сохраняют порядок вставки — это меняет поведение."
Паттерн анализа на собеседовании
Ожидаемый формат
Анализ сложности алгоритмов появляется на собеседованиях по разработке программного обеспечения. Сильный ответ следует четырёхчастному паттерну:
1. Сформулируйте текущую сложность — O(?) для времени, O(?) для пространства.
2. Объясните почему — определите конкретную конструкцию, ответственную за это (вложенный цикл, линейное сканирование в цикле, рекурсивное ветвление).
3. Предложите оптимизацию — назовите изменение и структуру данных или алгоритм, который оно вводит.
4. Сформулируйте новую сложность — после исправления, какова временная & пространственная сложность?
Пример:
Код: [функция, которая проверяет членство в списке внутри цикла]
Текущая: O(N²) — `item in seen_list` это O(N) на проверку × N итераций
Оптимизация: замените seen_list на seen_set (хеш-множество)
После: O(N) — проверка членства в множестве это O(1)Этот навык переносится за пределы собеседований: проверка кода с учётом сложности, дизайн архитектуры, отладка производительности, аудиты безопасности. Любая система, которая обрабатывает входы переменного размера, выигрывает от неё.
Этот урок соединяется дальше с курсом unhamming, который применяет этот точный паттерн к расследованию рабочих дефектов на 60+ проектах с открытым исходным кодом.
Собеседование: анализ has_common_element
Примените четырёхчастный формат собеседования к этой функции:
def has_common_element(list_a, list_b):
for item in list_a:
for other in list_b:
if item == other:
return True
return False