🗂

【競プロ】FastScannerの実装

2025/11/30に公開

import java.util.*;

// 中略
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();

こういう、入力を受け取るScannerを高速化する手法です。

「そんな効果あるか？」と半信半疑だったのですが、ものによっては2200msくらいでギリギリTLEだったものが300ms以下になったのでだいぶ早くなるみたいです。
特にテストケースがT回で、その中で入力を何度も受け取る系は早くなりそうです。

クラス定義

class FastScanner{
    private final InputStream in;
    private final byte[] buffer = new byte[1 << 16];
    private int pos = 0, len = 0;

    public FastScanner(InputStream in){
        this.in = in;
    }

    private int read() throws IOException{
        if(this.pos >= this.len){
            this.len = this.in.read(buffer);
            this.pos = 0;
            if(this.len <= 0) return -1;
        }
        return buffer[this.pos++];
    }

    long nextLong() throws IOException{
        int c;
        while((c = read()) <= ' '){ // 空白をスキップ
            if(c == -1) return Long.MIN_VALUE;
        }
        boolean minus = false;
        if(c == '-'){
            minus = true;
            c = read();
        }
        long val = c - '0';
        while((c = read()) > ' '){
            val = val * 10 + (c - '0');
        }
        return minus ? -val : val;
    }

    int nextInt() throws IOException{
        return (int)nextLong();
    }

    String next() throws IOException{
        int c;
        while((c = read()) <= ' '){
            if(c == -1) return null;
        }

        StringBuilder sb = new StringBuilder();
        sb.append((char)c);
        while((c = read()) > ' '){
            sb.append((char)c);
        }

        return sb.toString();
    }

    double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }

    float nextFloat() throws IOException{
        return Float.parseFloat(next());
    }
}

なぜ早くなるのか？

一言で言うと安全装置をすべて外したからです。
この入力はホントにint型にして大丈夫？とか、その辺の正規表現チェックをすっ飛ばしているので早くなっている...らしい。

後は1つ1つ読み込むのではなく、ある程度まとめてドバっと読み込み、それをクラス内に保持しておくのでI/O効率が良いのもミソ

コード解説

private final InputStream in; // 標準入力のクラス(System.in)
private final byte[] buffer = new byte[1 << 16];　// ドバっと読み込む保存先
private int pos = 0, len = 0;　// bufferの読み込み完了位置と、サイズを示す変数

private int read() throws IOException{
    if(this.pos >= this.len){
        this.len = this.in.read(buffer);
        this.pos = 0;
        if(this.len <= 0) return -1;
    }
    return buffer[this.pos++];
}

読み込み完了位置がbufferの最大を超えていたら、標準入力からbufferへ次の入力をさせる
read()を呼ばれるたびに読み込み完了位置を進めつつ、1バイト返す

long nextLong() throws IOException{
    int c;
    while((c = read()) <= ' '){ // 空白をスキップ
        if(c == -1) return Long.MIN_VALUE;
    }
    boolean minus = false;
    if(c == '-'){
        minus = true;
        c = read();
    }
    long val = c - '0';
    while((c = read()) > ' '){
        val = val * 10 + (c - '0');
    }
    return minus ? -val : val;
}

空白はスキップする
1バイト目がcharにすると - の時はminusフラグをオンにして次の文字を読み込む
- int cには文字コードに相当するものが格納される
- '-'の文字リテラルはchar型だが、intと比較するときはその文字コードのintとして比較できる
次の空白が来るまで10進数になるように元の値を10倍して1の位を追加する操作を繰り返す
- int cを文字リテラルと演算することで実質的にcharへ変換する
- char型を数値型に変換するときは、'0'とのマイナス演算を行えばよい

※
nextは同様のことをStringBuilderを使って行っているだけ、それ以外はほかのメソッドで得られた結果をparseして返却しているだけ

クラス定義

なぜ早くなるのか？

コード解説

Discussion