Scalaで競技プログラミング（入出力編）

入出力編以外が出来るかは不明。

最近Scalaで競技プログラミングをしていて入出力とその周辺が遅くてはまったのでメモ。
たぶん内容自体はJavaの入出力とその周辺。

実行時間は以下で計る。

object Utility {
  def measureTime(func: => Unit): Long = {
    val start = System.currentTimeMillis()
    func
    return System.currentTimeMillis() - start
  }
}

単純な出力

object Main {
  def main(args: Array[String]): Unit = {
    val rnd = Random
    System.err.println(Utility.measureTime {
      for (_ <- 1 to 1000000) println(rnd.nextInt())
    } + "ms")
    val pw = new PrintWriter(System.out)
    System.err.println(Utility.measureTime {
      for (_ <- 1 to 1000000) pw.println(rnd.nextInt())
      pw.flush()
    } + "ms")
  }
}

結果

17045ms
389ms

単純なprintlnは遅い。

フォーマット付き出力

object Main {
  def main(args: Array[String]): Unit = {
    val rnd = Random
    val pw = new PrintWriter(System.out)
    System.err.println(Utility.measureTime {
      for (_ <- 1 to 1000000) pw.println(rnd.nextInt() + " " + rnd.nextInt())
    } + "ms")
    System.err.println(Utility.measureTime {
      for (_ <- 1 to 1000000) pw.println("%d %d".format(rnd.nextInt(), rnd.nextInt()))
    } + "ms")
    pw.flush()
  }

}

結果

1068ms
6627ms

Stringのformatは遅い。

入力

一行にIntがスペース区切りに二つで1000000行のファイルを読み込む

普通に読み込みsplitで区切る

object Main {
  def main(args: Array[String]): Unit = {
    System.err.println(Utility.measureTime {
      for (_ <- 1 to 1000000) readLine().split(' ')
    } + "ms")
  }
}

結果

2269ms

入力クラスを作って使う

以下のクラス使います

class InputReader(stream: InputStream) {
  private val reader = new BufferedReader(new InputStreamReader(stream))
  private var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}

object Main {
  def main(args: Array[String]): Unit = {
    val in = new InputReader(System.in)
    System.err.println(Utility.measureTime {
      for (_ <- 1 to 1000000) {
        val a, b = in.next().toInt
      }
    } + "ms")
  }
}

結果

1141ms

splitは遅い。

まとめ

入出力というよりはStringのformatとかsplitが遅くてはまっていた。
今現在はformatとsplitを使わないようにしながらPrintWriterとInputReaderを使うようにしている。