入力文字列をparseIntで解析する場合とScannerを使用する場合との速度の違い

プログラミングコンテストとかでjava.util.Scannerを使って入力の数値を取得しようとすると、どうしてもInteger.parseIntした場合より実行速度が遅くなってしまうということで、どの程度のものなのかを簡単に調べてみたメモ。

検証環境

CentOS 7のVM(VirtualBox on Windows 10 on Let's Note CF-SX2)上で、OpenJDK 1.8.0_131を使用して測定。

ソースコード

parseInt版

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    public static void main(String[] args) {
        long S = System.currentTimeMillis();

        try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            PrintWriter out = new PrintWriter(System.out)
        ) {
            String buf;
            while ((buf = in.readLine()) != null) {
                String[] tokens = buf.split(" ");
                for (String token : tokens) {
                    int num = Integer.parseInt(token);
                    System.out.println(num);
                }
            }
            out.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }

        long G = System.currentTimeMillis();
        System.err.println((G - S) + "ms");
    }
}

Scanner版

import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        long S = System.currentTimeMillis();

        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        while (sc.hasNextInt()) {
            int num = sc.nextInt();
            out.println(num);
        }
        out.flush();

        long G = System.currentTimeMillis();
        System.err.println((G - S) + "ms");
    }
}

入力データ

パターン1

あまり入力数が多くないところで、1行に1数値の場合と1行に5数値の場合のデータを用意して比較。例えば、1行に5数値で1,000行の場合のデータは以下のような感じになる。

1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
：
：
996 996 996 996 996
997 997 997 997 997
998 998 998 998 998
999 999 999 999 999
1000 1000 1000 1000 1000

パターン2

では、本当にScannerの方がどんなケースでも遅いのか、と思って以下のパターンを試してみた。

N=10,000、100,000～1,000,000の11ケースで以下のような入力を食わせてみた。

1
2
3
4
5
：
：
N-4
N-3
N-2
N-1
N

測定結果

パターン1

こちらは予想通りというか、Scanner版の方が実行速度がかかっている。

N	parseInt(1)	Scanner(1)	parseInt(5)	Scanner(5)
0	0	36
1000	40	98	82	131
2000	51	121	130	175
3000	65	126	160	191
4000	69	130	183	246
5000	76	141	191	242
6000	79	153	210	267
7000	83	150	229	289
8000	108	163	257	323
9000	113	169	292	330

パターン2

N=200,000から300,000の辺りで速度が逆転している。大量の入力に対しては、なぜかparseInt版の方が速度的には不利なようだ。

N	parseInt	Scanner
10000	117	172
100000	452	471
200000	619	690
300000	804	761
400000	957	862
500000	1157	1060
600000	1276	1122
700000	1512	1105
800000	1692	1188
900000	1891	1321
1000000	1976	1412