Решил я как-то на ночь порешать пару задач из архива и наткнулся вот на такое чудо: 439B - Devu, the Dumb Guy
Читаю задачу и думаю, что она делает на месте задачи B? Разве можно придумать задачу проще этой, засунуть её в тот же контест и поставить на место задачи А? Видимо можно, не знаю. Я решил сначала написать решение этой задачи чтобы убедиться, что я правильно её понял.
Первый раз я написал задачу на интах и в конце заменил инты на лонги. Получил WA на 8 тесте. Так как я не привык сразу же лезть в детали посылки и смотреть, что за тест такой сломал моё решение, сначала я поковырялся в своём коде и только после того, как не нашёл ничего неверного, полез смотреть детали посылки. И что я там вижу? Каким-то странным образом отправилось решение на интах и получилось переполнение. Ладно, едем дальше.
Второй раз я отправил решение на лонгах и наблюдал, как стремительно растёт циферка в надписи Выполняется на тесте x Увы, но я получил TL на тесте 29. Было обидно, вот честно. Опять же я полез в свой код, только уже искать не баг, а пути оптимизации. Решил вместо Arrays.sort(), который примитивы сортирует quicksort'ом, написать сортировку подсчётом, благо в худшем случае я потрачу на N памяти больше и ускорю сортировку примерно в log N раз (напомню, 1 <= N <= 10^5, 0 <= log N < 17).
И что на этот раз? Решение отработало более чем в 10 раз быстрее, чем с Arrays.sort(). Всё дело, конечно, в асимптотике O(N^2) при сортировке quicksort'ом в худшем случае.
Если так прикинуть, на яве тоже должно всё решаться на уровне библиотечных алгоритмов. Замена массива int[] на List<Integer> это подтвердила. Ведь Collections.sort(), применяемый для листов, использует алгоритм сортировки слиянием (или, что чаще случается, TimSort'ом). Использовав такой подход, я замедлил своё решение примерно в 1.5-2 раза, но избавился от сортировки подсчётом.
А теперь давайте вспомним, что в Java 8 есть такая замечательная вещь как Stream API. Использовав её в этой задаче, мы можем ввести данные, отсортировать их и собрать в один список. Также в Stream API есть версия стрима, которая работает с лонгами, тем самым хранит в себе не ссылки, а примитивы, к тому же обладает рядом дополнительных методов. К слову, такая версия сортирует лонги методом быстрой сортировки (в то время как объектный стрим сортирует так же, как Collections.sort()), и мы можем наблюдать, как решение ломается (или чинится) из-за того, что мы всего лишь поменяли местами две строки:
boxed() — запаковывает стрим примитивов в объектный (LongStream -> Stream<Long>)
sorted() — собственно, сортирует стрим
Думаю, нулевая версия, основанная на интах, никому не будет интересна, вот все последующие версии:
Array TL: 12608743
Array AC: 12608824
Stream TL: 12609313
Stream AC: 12609319
Версия автора (C++): 6814439
Он использовал std::sort. Практически полный аналог моего первого решения.
Что я вынес из этого и хочу сказать вам:
Если у вас есть риск влететь в ТЛ и в коде есть сортировка, при этом у вас есть запас по памяти и эту сортировку можно выполнить методом сортировки подсчётом, используйте его. Вы съедите немного больше памяти, но зато будете уверены, что если ваш алгоритм не заходит, значит дело, скорее всего, не в сортировке. Да и это к тому же сортировка за O(N + макс. значение N) без единого сравнения.
Всем, кто дочитал, спасибо. =)
UPD 1: Как правильно заметил Gassa, вывод получился не совсем такой, какой я собирался вынести в начале написания этой статьи, поэтому добавлю:
- Проблема: в Java встроенная сортировка примитивных типов может работать за квадрат.
- Стандартное решение: использовать сортировку объектов за O(N log N).
- Предлагаемое решение: использовать сортировку подсчётом там, где это будет быстрее. (Кстати, в очень многих задачах)
Также аналогичное обсуждение, оказывается, было здесь: link
