Почему я полюбил сортировку подсчётом

Revision ru10, by jvmusin, 2015-08-20 15:22:56

Решил я как-то на ночь порешать пару задач из архива и наткнулся вот на такое чудо: 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

Tags java, сортировка, anti-quicksort

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru10 Russian jvmusin 2015-08-20 15:22:56 2 Мелкая правка: ' -> Stream<Long>)<br/>\n_' -> ' -> Stream\<Long\>)<br/>\n_'
ru9 Russian jvmusin 2015-08-20 08:09:50 4 Мелкая правка: 'совсем таким, какой я ' -> 'совсем такой, какой я '
ru8 Russian jvmusin 2015-08-20 07:49:56 832
ru7 Russian jvmusin 2015-08-20 01:42:48 91
ru6 Russian jvmusin 2015-08-20 01:27:28 19 Мелкая правка: 'а за **O(N)** без е' -> 'а за **O(N + макс. значение N)** без е'
ru5 Russian jvmusin 2015-08-20 01:21:23 12 Мелкая правка: 'вке. Да и к это тому же с' -> 'вке. Да и это к тому же с'
ru4 Russian jvmusin 2015-08-20 01:17:58 38 Мелкая правка: 'ировка за O(N) без едино' -> 'ировка за **O(N)** без едино'
ru3 Russian jvmusin 2015-08-20 01:16:42 286
ru2 Russian jvmusin 2015-08-20 01:04:09 37
ru1 Russian jvmusin 2015-08-20 00:57:15 3601 Первая редакция (опубликовано)