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

Автор frp, 11 лет назад, По-русски

Всем привет. Опять пишу о Scala и ее быстродействии. На этот раз о производительности ввода-вывода, о быстродействии, или, точнее, медленнодействии println и java.util.Scanner.

История о выводе

Решал я задачу. Единственной интересной для нас особенностью ее является то, что в ней возникает необходимость вывести миллион чисел. Если кратко, то мое решение получает список чисел, который затем нужно вывести, каждое число в новой строке, и на обеих концах списка — барьерные элементы (-1), которые выводить не нужно. Этот список — это list типа scala.collection.mutable.LinkedList[Int]. Первая попытка, самая очевидная:

    var next = list.next
    while (next.elem != -1) {
      println(next.elem)
      next = next.next
    }

Конечно же, попытка эта успешно обламывается с TLE.

Оказывается, println медленный. Заместо этого создаю StringBuilder и запихиваю в него результаты, и лишь затем вывожу при помощи print:

    var next = list.next
    val sb = new StringBuilder()
    while (next.elem != -1) {
      sb.append(next.elem).append("\n")
      next = next.next
    }
    print(sb)

Результат: полное решение. Попался на подобном во второй раз. Когда было в первый раз, я попался одновременно и на этом, и на вводе.

История о вводе

Решал я задачу. На скале решать я начал совсем недавно, поэтому о подводных камнях Scala и JVM вообще в плане быстродействия знаю немного. Первая посылка дала TLE#23. Это было из-за вывода, та же проблема, что описана выше, но я-то тогда этого не знал и стал думать на ввод, который делался при помощи такой функции:

def readLineOfNums(): Array[Long] = readLine().split(" ").map(_.toLong)

Что, очевидно, далеко не идеально по быстродействию, зато очень легко пишется и сравнительно удобно в использовании. Решил я вместо этого использовать java.util.Scanner, знакомый мне с Java, но ни разу не использованный в серьезных боевых условиях. И тут меня ждал неожиданный фейл: TLE#11. Как оказалось, на самом деле java.util.Scanner очень и очень тормозный, гораздо тормознее, чем мой способ. Я сдал эту задачу после того, как вернул обратно свой разбор ввода и пофиксил вывод.

Выводы

  1. println медленный. Если запихнуть всё в StringBuilder и затем вывести, будет быстрее. Да вот только это создает серьезные неудобства, когда вывода слишком много, чтобы одновременно весь хранить в памяти. Проблема явно актуальна и для Java, т.к. Scala-вский println вызывает System.out.println.
  2. java.util.Scanner медленный, причем аж до такой степени, что readLine().split(" ").map(_.toLong) его обгоняет. Не стоит его использовать там, где присутствует большой ввод. Мне весьма неочевидно, что же делает его таким медленным.
  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

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

Я, конечно, Scala не знаю, но в первом TL'ящемся решении видны очевидные косяки "если бы это было написано на Java" — зачем каждый раз создавать новый LinkedList? Зачем вообще использовать LinkedList, ведь итерации по нему даже в Java раза в 3 медленее? И самый важный вопрос — зачем в этой задаче вообще структура данных? Мне кажется, вы просто ССЗБ и дело совсем не в библиотеках. Поправьте, если ошибаюсь. Можно найти решения на Java с LinkedList и они тоже совсем не быстрые, но LinkedList они на каждый чих не создают. Попробуйте переписать решение с использованием ArrayList или массивов с выводом прямо в PrintWriter. Наверно, буст будет заметный. А что касается ввода через Scanner — да, оно может быть совсем не быстрым для такого объёма данных даже для Java.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    1. scala.collection.mutable.LinkedList — это не java.util.LinkedList, не стОит путать. Каждый раз создавать новый scala.collection.mutable.LinkedList — это и есть его правильное использование.

    2. Можно было вместо этого обойтись двумя векторами. Быстрее это или так же в Scala — не знаю. Может быть, и ССЗБ. Обычно пишу соревнования на C++ (с другими языками играюсь только в архиве), а там разница в быстродействи итерирования по std::vector и std::list обычно пренебрежимо мала (хотя лучше при прочих равных все-таки выбирать вектор).

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      1. Если scala.collection.mutable.LinkedList это связный список на объектах (как и LinkedList в Java), то это точно первый гвоздь в производительность. Хотя бы для себя попробуйте выяснить — тормозит ли финальная итерация по нему или такой интересный способ добавления элементов.
      2. Вот что уж, а пытаться проводить аналогии между Scala и плюсами наверно не стоит в плане производительности + см пункт 1 ...
      3. Честно, очень слабо верится, что print в Java может быть причиной тормозов, когда всё остальное летает. Посмотрите хотя бы скорость чужих решения на Java даже с LinkedList.