HHeLiBeXの日記 正道編

日々の記憶の記録とメモ‥

入力文字列を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

f:id:hhelibex:20171027220416p:plain

パターン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

f:id:hhelibex:20171027220508p:plain