Всем привет. Опять пишу о 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 очень и очень тормозный, гораздо тормознее, чем мой способ. Я сдал эту задачу после того, как вернул обратно свой разбор ввода и пофиксил вывод.
Выводы
- println медленный. Если запихнуть всё в StringBuilder и затем вывести, будет быстрее. Да вот только это создает серьезные неудобства, когда вывода слишком много, чтобы одновременно весь хранить в памяти. Проблема явно актуальна и для Java, т.к. Scala-вский println вызывает System.out.println.
- java.util.Scanner медленный, причем аж до такой степени, что readLine().split(" ").map(_.toLong) его обгоняет. Не стоит его использовать там, где присутствует большой ввод. Мне весьма неочевидно, что же делает его таким медленным.
Я, конечно, Scala не знаю, но в первом TL'ящемся решении видны очевидные косяки "если бы это было написано на Java" — зачем каждый раз создавать новый LinkedList? Зачем вообще использовать LinkedList, ведь итерации по нему даже в Java раза в 3 медленее? И самый важный вопрос — зачем в этой задаче вообще структура данных? Мне кажется, вы просто ССЗБ и дело совсем не в библиотеках. Поправьте, если ошибаюсь. Можно найти решения на Java с LinkedList и они тоже совсем не быстрые, но LinkedList они на каждый чих не создают. Попробуйте переписать решение с использованием ArrayList или массивов с выводом прямо в PrintWriter. Наверно, буст будет заметный. А что касается ввода через Scanner — да, оно может быть совсем не быстрым для такого объёма данных даже для Java.
scala.collection.mutable.LinkedList — это не java.util.LinkedList, не стОит путать. Каждый раз создавать новый scala.collection.mutable.LinkedList — это и есть его правильное использование.
Можно было вместо этого обойтись двумя векторами. Быстрее это или так же в Scala — не знаю. Может быть, и ССЗБ. Обычно пишу соревнования на C++ (с другими языками играюсь только в архиве), а там разница в быстродействи итерирования по std::vector и std::list обычно пренебрежимо мала (хотя лучше при прочих равных все-таки выбирать вектор).
На чистых массивах. Вывод через println точно так же валится на тесте №31. На массивах и StringBuilder работает таки быстрее: вместо 1092 мс дает 720 мс (однако при данных временных ограничениях это не играет роли).
Но таки есть у людей посылки на Java с выводом через println, которые проходят: http://codeforces.me/contest/265/submission/2966669