Всем привет. Опять пишу о 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) его обгоняет. Не стоит его использовать там, где присутствует большой ввод. Мне весьма неочевидно, что же делает его таким медленным.