Кейс: сортировка списка из 50 элементов уронила API под нагрузкой

Эндпоинт отдавал список товаров с фильтрами, отсортированный по нескольким полям через кастомный Comparator. На стейджинге с тестовыми данными всё летало — список редко превышал сотню элементов.

В проде под нагрузкой сортировка вызывалась внутри цикла обработки batch-запроса: на каждый элемент внешнего списка заново запускалась сортировка внутреннего. Снаружи 2000 запросов в батче, внутри сортировка 50 элементов — итого 100 000 операций сравнения там, где ожидали 50.

Проблему нашли не через профилировщик, а через логи: время ответа росло нелинейно с размером батча, хотя сложность отдельной сортировки O(n log n) выглядела безобидно на бумаге. Вынесли сортировку за пределы цикла — считали её один раз для объединённого списка.

List result = new ArrayList<>(); for (Batch batch : batches) { List items = batch.getItems(); items.sort(comparator); result.addAll(items); }

Ловушка на собеседовании: спросят, почему O(n log n) внутри цикла на m итераций — это не O(n log n), а O(m · n log n), и как определить это по описанию кода без замера. Ответ — смотреть не на асимптотику одной операции, а на то, где она вызывается повторно.

Асимптотика отдельной функции ничего не говорит о её месте в цикле — считать нужно вложенность целиком.

Тренажёр: 600 вопросов, мок с таймером, план повторов

senior·base — что спрашивают на самом деле

В этом посте были ссылки, но мы их удалили по правилам Сетки