Блог пользователя jvmusin

Автор jvmusin, история, 9 лет назад, По-русски

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

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

mapToObj вам в помощь, чтобы обойтись без boxed(). Более выразительный способ, чтобы подчеркнуть явный переход к объектам, для которых логично было предположить, что сортировка работает привычным способом. Ну или можно сразу создать стрим из Long и не париться:

Stream.iterate(0L,t->t+1).limit(n).map(l -> in.readLong()).sorted().collect(Collectors.toList());

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Если вам хочется выразительнее, написали бы Stream.generate(in::readLong).limit(n).sorted().collect(Collectors.toList());

    Я же говорю не о выразительности, а о разнице в работе алгоритмов сортировки.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Эту тему на CF не пинал только ленивый. За то, что вы не удосужились поискать существующие обсуждения — вам минус, а за "исследование" аналогичной проблемы со стримами — плюс. Собственно я и прошел бы мимо этого поста, если бы не самая удачная, на мой взгляд, попытка решения проблемы стримами.

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        А ещё стримы были бы гораздо более выгодны, если бы тестирующие системы не ограничивали количество доступных потоков до одного. Иначе можно было бы использовать параллелизацию. А вообще код с ними смотрится несколько красивее и проще, как по мне.

        В любом случае спасибо за уделённое внимание =)

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Зачастую они не ограничивают число потоков, а считают суммарное время всех потоков. Параллельте сколько влезет.

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            Возможно вы и правы, вот только я на таком тесте ещё не видел, чтобы тестирующая система отдала мне больше одного потока 12619757

            Не поделитесь примерами систем, где распараллеливание работает как вы говорите?

»
9 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Stream, сортировка подсчётом и остальной текст поста — это интересно, но заслоняет основную мысль, которая могла бы быть такой.

  • Проблема: в Java встроенная сортировка примитивных типов может работать за квадрат.

  • Стандартное решение: использовать сортировку объектов.

Кстати, вот аналогичное обсуждение этой же задачи, но без лирических отступлений.