Решил я как-то на ночь порешать пару задач из архива и наткнулся вот на такое чудо: 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
mapToObjвам в помощь, чтобы обойтись без boxed(). Более выразительный способ, чтобы подчеркнуть явный переход к объектам, для которых логично было предположить, что сортировка работает привычным способом. Ну или можно сразу создать стрим из Long и не париться:Stream.iterate(0L,t->t+1).limit(n).map(l -> in.readLong()).sorted().collect(Collectors.toList());Если вам хочется выразительнее, написали бы
Stream.generate(in::readLong).limit(n).sorted().collect(Collectors.toList());Я же говорю не о выразительности, а о разнице в работе алгоритмов сортировки.
Эту тему на CF не пинал только ленивый. За то, что вы не удосужились поискать существующие обсуждения — вам минус, а за "исследование" аналогичной проблемы со стримами — плюс. Собственно я и прошел бы мимо этого поста, если бы не самая удачная, на мой взгляд, попытка решения проблемы стримами.
А ещё стримы были бы гораздо более выгодны, если бы тестирующие системы не ограничивали количество доступных потоков до одного. Иначе можно было бы использовать параллелизацию. А вообще код с ними смотрится несколько красивее и проще, как по мне.
В любом случае спасибо за уделённое внимание =)
Зачастую они не ограничивают число потоков, а считают суммарное время всех потоков. Параллельте сколько влезет.
Возможно вы и правы, вот только я на таком тесте ещё не видел, чтобы тестирующая система отдала мне больше одного потока 12619757
Не поделитесь примерами систем, где распараллеливание работает как вы говорите?
Stream, сортировка подсчётом и остальной текст поста — это интересно, но заслоняет основную мысль, которая могла бы быть такой.
Проблема: в Java встроенная сортировка примитивных типов может работать за квадрат.
Стандартное решение: использовать сортировку объектов.
Кстати, вот аналогичное обсуждение этой же задачи, но без лирических отступлений.