Квадратичный код агента: как заметить его до прода

Агент решает задачу, тесты проходят, на десяти записях всё мгновенно. А потом в базе оказывается сто тысяч записей, и тот же код работает минуты. Чаще всего причина — квадратичная сложность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 загрузить пользователей вместе с заказами или выбрать их одним запросом по списку идентификаторов.

Чем заменить вложенный проход

Почти все такие места чинятся одним из четырёх приёмов. Их полезно знать по именам — тогда агенту можно сказать, что именно сделать, а не просить «ускорить».

  1. Множество или словарь для поиска. Один раз построить структуру по ключу, а дальше спрашивать её. Это случай с заказами и пользователями.
  2. Группировка за один проход. Вместо «для каждого клиента найти его заказы» пройти по заказам один раз и разложить их в словарь, где ключ — клиент, а значение — список. В Python для этого есть defaultdict(list), для подсчётов — Counter.
  3. Сортировка и один проход. Дубликаты, пересечения отрезков, ближайшие по времени события находятся проще, если данные сначала упорядочить66Сортировка стоит O(n log n). Для миллиона элементов это около двадцати миллионов сравнений — против тысячи миллиардов у попарного перебора. Поэтому «отсортировать и пройти один раз» почти всегда выгоднее вложенного цикла.: после сортировки кандидаты стоят рядом, и сравнивать нужно только соседей.
  4. Перенос работы в базу. Соединение таблиц, фильтр и подсчёт база сделает сама, по индексу и без передачи лишних строк в приложение. Цикл с запросом внутри почти всегда превращается в один запрос с 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))

7

Попросите агента написать такой замер вместе с кодом. Генератор тестовых данных на сто тысяч строк — пять минут его работы, а проверка превращается из чтения диффа в цифру.

В ревью ищите не ошибки синтаксиса, а вложенные проходы по одной и той же коллекции: цикл в цикле, метод поиска внутри map или filter, обращение к базе или к связанному объекту внутри цикла.

Запишите ожидаемый объём в правила проекта. Строка вида «таблицы orders и events содержат миллионы строк, не читай их целиком и не делай запросов в цикле» избавляет от половины таких находок88Квадратичный цикл — частный случай решения, которое агент принял молча, потому что в задаче не было цифр. Об архитектурных решениях того же рода — в статье о системном дизайне и спеках.. Как формулировать правила, чтобы агент их выполнял, рассказано в статье об AGENTS.md.

Как оценивать сложность, когда брать словарь, множество или кучу и как находить лишние вложенные циклы в коде агента — разбираем на курсе «Структуры данных и алгоритмы».

Курсы по теме

У каждого курса есть бесплатная часть: оставьте почту и начните сразу.

Рассылка

Раз в месяц — новые курсы, обновления программ и платформы. Отписаться можно в один клик из любого письма.

Начните учиться сегодня

Все курсы за 1500 ₽ в месяц. Доступ откроется сразу после оплаты, отменить можно в любой момент.

Для компаний — 5000 ₽ в месяц за сотрудника