Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Почему я разлюбил quicksort

Revision ru3, by Musin, 2015-08-20 01:16:42

Решил я как-то на ночь порешать пару задач из архива и наткнулся вот на такое чудо: link

Читаю задачу и думаю, что она делает на месте задачи 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)
sorted() — собственно, сортирует стрим

Думаю, нулевая версия, основанная на интах, никому не будет интересна, вот все последующие версии:
Array TL: link
Array AC: link
Stream TL: link
Stream AC: link

Версия автора (C++): link
Он использовал std::sort. Практически полный аналог моего первого решения.

Что я вынес из этого и хочу сказать вам:

Если у вас есть риск влететь в ТЛ и в коде есть сортировка, при этом у вас есть запас по памяти и эту сортировку можно выполнить методом сортировки подсчётом, используйте его (а можно и поразрядную сортировку написать, даже эффективнее будет в большинстве случаев). Вы съедите немного больше памяти, но зато будете уверены, что если ваш алгоритм не заходит, значит дело, скорее всего, не в сортировке. Да и к это тому же сортировка за O(N) без единого сравнения.

Всем, кто дочитал, спасибо. =)

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

History

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