てきとーな日記

2009-09-14

[]入出力 13:22

コンテストの問題をJavaで解くときに、ときどき入出力がボトルネックになってTLEするので、その解決策を色々試してみた

入力

1. Scanner

使いやすいけど、正規表現を用いているためとても遅い

100万個のint値読み込むだけで3.5sくらいかかった

2. Integer.parseInt(Scanner.next())

Scanner.nextInt()の代わりにInteger.parseInt(Scanner.next())とかやると、少し速くなって2sくらい

置換一発でできるので楽

3. BufferedReaderとStringTokenizerで自前Scannerを作る

IFMOのチームがこれをやっていたので試してみた

100万個のint値読み込みで0.5sくらいで、かなり高速

もちろんjava.utilのScannerを使う場合に比べてコード量が…

4. System.in.read()で一文字ずつ読みながら自前で読み込み

自分は今までこれをやってた

100万個のint値読み込みで0.3sくらい

String読み込みとかあると2の方が速いし、コード量がさらに…


というわけで今度からは入力でかいときは3番の自前Scannerを使うことにしよう

出力

1. System.out

100万個int出力で9秒とかかかってとても遅い

2. System.setOut(new PrintStream(new BufferedOutputStream(System.out)))

これを最初に書くだけで超速くなって1秒ちょいに!!

バッファリングするため、コンソールに出す場合すぐ出力されず残念なことになるから提出時のみ有効にするとかする必要が…

3. PrintWriter

IFMOのチームがこれを使っていた

なんと0.5sくらいに!

これもバッファリングするのでほげ

引数で改行時に自動フラッシュも可能だが、改行しないとフラッシュされない

使い慣れたsysoutが使えなくなるので残念

4. StringBuilder

出力を全てため込んで最後に一気に出す

0.3sくらいになったけどめんどくさい


3が一番よさそうだけどローカル実行の場合と、体が出力=sysoutと記憶してしまっていることを考えると2番の方がいいのかなぁ