競技プログラミングでは、与えられた問題を制限時間内に解くプログラムを書くことが求められます。なので速度を改善することが非常に重要です。アルゴリズムを改善することで速くなることが多いですが、それ以外の部分で高速化できることもあります。特に入出力は競技プログラミングにおいて必須ですが、実はかなり実行時間に影響します。アルゴリズム以外の原因でTLEを出さないためにも、入出力の高速化はとても大切です。
今回はKotlinにおける、高速な入出力について説明します。
Kotlinコード
自分は以下のようなコードを用いています。
import java.io.PrintWriter import java.util.* import kotlin.math.* fun PrintWriter.solve() { //ここにコードを書く //サンプル:数列を受け取って総和を出力するプログラム val n = nextInt() val a = Array(n) { nextInt() } println(a.sum()) } fun main() { val writer = PrintWriter(System.out, false) writer.solve() writer.flush() } // region Scanner private var st = StringTokenizer("") private val br = System.`in`.bufferedReader() fun next(): String { while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine()) return st.nextToken() } fun nextInt() = next().toInt() fun nextLong() = next().toLong() fun nextLine() = br.readLine()!! fun nextDouble() = next().toDouble() // endregion
まずは入力について。通常はreadLine関数が用いられますが、若干遅いです。そこでBufferedReaderを用いて入力を高速化します。
次に出力について。Kotlinに限った話ではないですが、出力のたびにflushをしているとかなり遅くなります。そのため、flushを最後の1回のみにすることで高速化できます。上のコードでは
val writer = PrintWriter(System.out, false)
のfalseの部分で、autoflushをオフにしています。
ただし、インタラクティブ問題では出力のたびにflushを行わないといけないので注意が必要です。
比較
この工夫によりどれだけ速くなるか実験してみました。時間計測にはAtCoderのコードテストを使用しました。
まずは入力です。250000個の1を読み込む時間を比較します。すると次のようになりました。
- 工夫なし 342ms 336ms 329ms
- 工夫あり 286ms 240ms 245ms
そこまで速くなっていないので、高速な入力に切り替えるメリットは少なそうです。ただ、この問題では最大2*106個の整数を受け取る上にTLが1.5秒なので、入力の高速化が必須になる場合もあります。
次は出力です。100000回Hello Worldを出力し、その時間を計測しました。
- 工夫なし 542ms 531ms 544ms
- 工夫あり 162ms 162ms 147ms
こちらはかなり差があります。100000回出力する問題は結構見かけるので、出力だけでも高速化しておくとよいでしょう。
(追記:2021/07/20)
一般的にはBufferedReaderを用いた方が速くなりますが、一部の問題ではreadLine関数を用いた方が速い場合もあるようです。例えば以下の問題です。
原因は不明ですが、インタラクティブ問題であることが関係していると推測します。問題に応じて入力に用いる方法を変える必要がありそうです。