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

Агент решает задачу, тесты проходят, на десяти записях всё мгновенно. А потом в базе оказывается сто тысяч записей, и тот же код работает минуты. Чаще всего причина — квадратичная сложность: время растёт не пропорционально данным, а как их квадрат.

Как он выглядит

Самый частый случай — поиск внутри цикла:

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:
        ...

Проверка в множестве почти мгновенная, и время снова растёт линейно.

Где ещё прячется квадрат

• list.remove() или in по списку внутри цикла;
• сортировка внутри цикла вместо одной сортировки снаружи;
• запрос к базе на каждую строку — та же история, только по сети;
• склейка строк в цикле через + в языках, где строка неизменяемая.

Как поймать до прода

Прикиньте рост: что будет, если данных станет в десять раз больше? Если ответ «работать станет в сто раз дольше» — перед вами квадрат. Проверьте на данных реального размера, а не на трёх строчках из теста. И в ревью ищите не ошибки синтаксиса, а вложенные проходы по одной и той же коллекции.

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