Квадратичный код агента: как заметить его до прода
Агент решает задачу, тесты проходят, на десяти записях всё мгновенно. А потом в базе оказывается сто тысяч записей, и тот же код работает минуты. Чаще всего причина — квадратичная сложность11Запись O(n²) описывает форму роста, а не точное время: во сколько раз вырастет число операций, если данных станет больше. Константы в ней отброшены, поэтому на малых объёмах «плохой» алгоритм может быть даже быстрее.: время растёт не пропорционально данным, а как их квадрат.
Как он выглядит
Самый частый случай — поиск внутри цикла:
for order in orders:
if order.user_id in [u.id for u in users]:
...
На каждый заказ код заново проходит по всем пользователям. Тысяча заказов и тысяча пользователей — миллион проверок. Десять тысяч на десять тысяч — сто миллионов.
Исправление — один раз построить множество:
user_ids = {u.id for u in users}
for order in orders:
if order.user_id in user_ids:
...
Проверка в множестве22Множество хранит только уникальные значения: повторяющиеся user_id исчезнут. В этом примере нужен только ответ «есть или нет», поэтому это не меняет результат. Множества в Python. почти мгновенная, и время снова растёт линейно.
В JavaScript и TypeScript та же ошибка выглядит ещё невиннее, потому что прячется в одной строке:
const active = orders.filter((order) =>
users.find((user) => user.id === order.userId)
);
filter обходит заказы, find на каждом шаге обходит пользователей. Лечится так же: new Set(users.map((user) => user.id)) снаружи и ids.has(order.userId) внутри. Если нужен не ответ «есть или нет», а сам пользователь, вместо множества берут Map или словарь33Поиск в множестве и словаре быстрый, потому что они построены на хэш-таблице: место элемента вычисляется по его значению, а не ищется перебором. Плата за это — дополнительная память и требование, чтобы ключи были неизменяемыми.: ключ — идентификатор, значение — объект.
Почему тесты его не ловят
Квадратичный код — правильный код. Он возвращает верный результат, просто долго. А тесты, которые пишет агент, проверяют именно результат и почти всегда на трёх-пяти записях: так тест читается и работает быстро. На таком объёме разницу между линейным и квадратичным алгоритмом не видно ни глазами, ни секундомером.
Так растёт число операций для вложенного прохода по одной коллекции:
| Записей | Линейно | Квадратично |
|---|---|---|
| 10 | 10 | 100 |
| 1 000 | 1 000 | 1 000 000 |
| 100 000 | 100 000 | 10 000 000 000 |
Первая строка — это тест. Вторая — демо для заказчика: миллион простых операций всё ещё выполняется за доли секунды. Третья — обычная таблица в рабочей базе, и десять миллиардов операций — это десятки секунд даже в быстром компилируемом языке и многие минуты в Python.
Агенту не с чего догадаться, какая из трёх строк ваша. Если в задаче не сказано, сколько будет данных, он выбирает самый короткий и читаемый вариант — и это разумно. Размер данных — такое же требование, как формат ответа, и его стоит писать в задаче прямо: «в таблице заказов до миллиона строк».
Где ещё прячется квадрат
Вложенный цикл по двум спискам заметить нетрудно. Хуже, когда второй проход спрятан внутри метода, который выглядит как одна операция.
- Операции над списком внутри цикла.
x in list,list.remove(x),list.index(x),list.insert(0, x)иlist.pop(0)в Python,includes,indexOf,findиshiftв JavaScript — каждая проходит по списку или сдвигает его целиком. - Сортировка внутри цикла вместо одной сортировки снаружи. Частый вариант — «добавили элемент и пересортировали» на каждом шаге.
- Накопление через копирование.
result = result + [x]в Python и[...acc, x]вreduceкаждый раз создают новый массив и копируют в него всё накопленное44В pandas та же ловушка —pd.concatв цикле: каждый вызов копирует всё, что уже накоплено. Собирайте куски в обычный список и объединяйте один раз после цикла.. - Склейка строк в цикле через
+в языках, где строка неизменяемая. Надёжнее собрать части в список и соединить один раз:"".join(parts). - Запрос к базе на каждую строку. Та же история, только каждая итерация ещё и ходит по сети.
- Попарное сравнение «каждый с каждым»: поиск дубликатов, пересечений, ближайших соседей.
Лучше всего запрос в цикле прячет ORM, как в этом примере:
orders = Order.objects.all()
for order in orders:
print(order.user.name) # отдельный запрос на каждый заказ
В коде нет ни одного вложенного цикла, а база получает тысячу и один запрос55Эту ошибку называют проблемой N+1: один запрос за списком и ещё N — за связанной записью каждой строки. В ORM её лечат жадной загрузкой: select_related и prefetch_related в Django, include в Prisma. на тысячу заказов. Исправляется одним соединением: попросить ORM загрузить пользователей вместе с заказами или выбрать их одним запросом по списку идентификаторов.
Чем заменить вложенный проход
Почти все такие места чинятся одним из четырёх приёмов. Их полезно знать по именам — тогда агенту можно сказать, что именно сделать, а не просить «ускорить».
- Множество или словарь для поиска. Один раз построить структуру по ключу, а дальше спрашивать её. Это случай с заказами и пользователями.
- Группировка за один проход. Вместо «для каждого клиента найти его заказы» пройти по заказам один раз и разложить их в словарь, где ключ — клиент, а значение — список. В Python для этого есть
defaultdict(list), для подсчётов —Counter. - Сортировка и один проход. Дубликаты, пересечения отрезков, ближайшие по времени события находятся проще, если данные сначала упорядочить66Сортировка стоит O(n log n). Для миллиона элементов это около двадцати миллионов сравнений — против тысячи миллиардов у попарного перебора. Поэтому «отсортировать и пройти один раз» почти всегда выгоднее вложенного цикла.: после сортировки кандидаты стоят рядом, и сравнивать нужно только соседей.
- Перенос работы в базу. Соединение таблиц, фильтр и подсчёт база сделает сама, по индексу и без передачи лишних строк в приложение. Цикл с запросом внутри почти всегда превращается в один запрос с
JOINилиWHERE id IN (...).
У каждого приёма есть цена: словарь занимает память, сортировка меняет порядок, а запрос с соединением нужно уметь проверить. О том, как убедиться, что такой запрос считает верно, — в статье о проверке SQL от агента.
Когда квадрат не страшен
Не каждый вложенный цикл — ошибка. Если коллекция маленькая и расти ей некуда — двадцать полей формы, семь дней недели, десяток тарифов, — квадратичный код останется быстрым навсегда, а простой вариант легче читать и проверять.
Для каждого вложенного цикла нужно проверить, чем ограничен размер данных, которые он обходит. Если ограничение задаёт предметная область, всё в порядке. Если размер определяют пользователи, время или внешний источник — файл, который загрузит клиент, история заказов за пять лет, — считайте, что данных будет много.
Обратная крайность тоже встречается: агент, которого попросили «оптимизировать», заменяет понятный код на кэши и индексы там, где обрабатывается пятьдесят строк. Сначала замер, потом оптимизация.
Как поймать до прода
Прикиньте рост. Что будет, если данных станет в десять раз больше? Если ответ «работать станет в сто раз дольше» — перед вами квадрат.
Проверьте на данных реального размера, а не на трёх строчках из теста. Самый дешёвый способ — эксперимент с удвоением: запустить функцию на тысяче, двух и четырёх тысячах записей и сравнить время.
import time
for n in (1_000, 2_000, 4_000, 8_000):
data = make_orders(n)
start = time.perf_counter()
build_report(data)
print(n, round(time.perf_counter() - start, 3))Попросите агента написать такой замер вместе с кодом. Генератор тестовых данных на сто тысяч строк — пять минут его работы, а проверка превращается из чтения диффа в цифру.
В ревью ищите не ошибки синтаксиса, а вложенные проходы по одной и той же коллекции: цикл в цикле, метод поиска внутри map или filter, обращение к базе или к связанному объекту внутри цикла.
Запишите ожидаемый объём в правила проекта. Строка вида «таблицы orders и events содержат миллионы строк, не читай их целиком и не делай запросов в цикле» избавляет от половины таких находок88Квадратичный цикл — частный случай решения, которое агент принял молча, потому что в задаче не было цифр. Об архитектурных решениях того же рода — в статье о системном дизайне и спеках.. Как формулировать правила, чтобы агент их выполнял, рассказано в статье об AGENTS.md.
Как оценивать сложность, когда брать словарь, множество или кучу и как находить лишние вложенные циклы в коде агента — разбираем на курсе «Структуры данных и алгоритмы».
Курсы по теме
У каждого курса есть бесплатная часть: оставьте почту и начните сразу.
Структуры данных и алгоритмы
База любого собеседованияСредний уровень11 уроков бесплатно →
Как проверить SQL, который написал агент. Запрос агента выполняется без ошибок — это ещё не значит, что он считает правильно. Пять мест, где SQL ошибается молча.
Что писать в AGENTS.md, чтобы агент работал лучше. Как AI-агенты читают AGENTS.md и CLAUDE.md, какие правила меняют их поведение, чего в файл не писать и как держать его коротким. С примерами правил.
Системный дизайн — недостающая половина spec-driven development. Агент пишет код по спеке, но про нагрузку, кэш и отказы спрашивать не станет. Что должно быть в архитектурной части спеки.