Very Fast Input Scanner
Difference between en1 and en2, changed 2 character(s)
Hi there! Couple of days ago I was solving problem [796C-Bank Hacking](http://codeforces.com/problemset/problem/796/C).↵
I came up with O(nlog(n)) order solution, but it failed with Time Limit Exceeded status. The max input size was 3*10^5, which implies that order O(n*log(n)) algorithm must fit into time limit. The tutorial for the contest also mentioned the same order solution.  After a few hours of debugging, I have realized that the problem is in input reading part. Well, my code used buil
dt in BufferedReader in java:↵

~~~~~↵
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));↵
int n =  Integer.parseInt(br.readLine());↵
Bank banks[] = new Bank[n];↵
String tokens[] = br.readLine().split(" ");↵
List<Integer> g[] = new List[n]; ↵
int max = Integer.MIN_VALUE; ↵
for(int i =0 ;i<n;i++) {↵
g[i] = new ArrayList<>(); ↵
int val = Integer.parseInt(tokens[i]);↵
max = Math.max(max, val); ↵
banks[i] = new Bank(i, val);↵
} ↵
for(int i = 0;i<n-1;i++){↵
tokens = br.readLine().split(" ");↵
int a = Integer.parseInt(tokens[0])-1;↵
int b = Integer.parseInt(tokens[1])-1;↵
g[a].add(b);↵
g[b].add(a);↵
}↵
~~~~~↵
The code slice about already consumed about 800 ms for the maximum size input. After I have submitted a linear time alternative solution, but I still decided to find more faster way of reading. I have found [williamfiset](https://github.com/williamfiset/FastJavaIO/blob/master/src/main/java/fastjavaio/InputReader.java) 's InputReader which claimed to be much faster than the BufferedReader. Finally I decided to write my own FastScanner inspired with his idea.↵
Well here it is (Currently I have just implemented it for Integers):↵

~~~~~↵
import java.io.*;↵
import java.util.*;↵

public class FastScanner {↵

    static final int DEFAULT_BUFF = 1024, EOF = -1, INT_MIN = 48, INT_MAX = 57;↵
    static final byte NEG = 45;↵
    static final int[] ints = new int[58];↵

    static {↵
        int value = 0;↵
        for (int i = 48; i < 58; i++) {↵
            ints[i] = value++;↵
        }↵
    }↵

    InputStream stream;↵

    byte[] buff;↵
    int buffPtr;↵

    public FastScanner(InputStream stream) {↵
        this.stream = stream;↵
        this.buff = new byte[DEFAULT_BUFF];↵
        this.buffPtr = -1;↵
    }↵

    public int nextInt() throws IOException {↵
        int val = 0;↵
        int sign = readNonDigits();↵
        while (isDigit(buff[buffPtr]) && buff[buffPtr] != EOF) {↵
            val = (val << 3) + (val << 1) + ints[buff[buffPtr]];↵
            buffPtr++;↵
            if (buffPtr == buff.length) {↵
                updateBuff();↵
            }↵
        }↵
        return val*sign;↵
    }↵

    private int readNonDigits() throws IOException {↵
        if (buffPtr == -1 || buffPtr == buff.length) {↵
            updateBuff();↵
        }↵
        if (buff[buffPtr] == EOF) {↵
            throw new IOException("End of stream reached");↵
        }↵
        int signByte = -1;↵
        while (!isDigit(buff[buffPtr])) {↵
            signByte = buff[buffPtr];↵
            buffPtr++;↵
            if (buffPtr >= buff.length) {↵
                updateBuff();↵
            }↵
            if (buff[buffPtr] == EOF) {↵
                throw new IOException("End of stream reached");↵
            }↵
        }↵
        if(signByte == NEG) return -1;↵
        return 1;↵
    }↵

    public void close() throws IOException {↵
        stream.close();↵
    }↵

    private boolean isDigit(int b) {↵
        return b >= INT_MIN && b <= INT_MAX;↵
    }↵

    private void updateBuff() throws IOException {↵
        buffPtr = 0;↵
        stream.read(buff);↵
    }↵
}↵

~~~~~↵

The FastScanner class in my code worked very fast and the maximum size input reading time has reduced up to 47 ms. As a result I have got accepted even with O(nlog(n)) order solution, just by replacing the reading part by the following code slice:↵

~~~~~↵
FastScanner in = new FastScanner(System.in);↵
int n =  in.nextInt();↵
Bank banks[] = new Bank[n];↵
List<Integer> g[] = new List[n]; ↵
for(int i =0 ;i<n;i++) {↵
g[i] = new ArrayList<>(); ↵
int val = in.nextInt();;↵
banks[i] = new Bank(i, val+2);↵
} ↵
for(int i = 0;i<n-1;i++){↵
int a = in.nextInt()-1;↵
int b = in.nextInt()-1;↵
g[a].add(b);↵
g[b].add(a);↵
}↵
~~~~~↵
You may find my last submission [here](http://codeforces.com/contest/796/submission/27793950) if you want.↵

Further I plan to upgrade and test my FastScanner, and never use BufferedReader when fast reading is important.↵

Thank you for attention. ↵




History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English ZhassanB 2017-06-16 08:06:09 6 Tiny change: 'de slice about already c' -> 'de slice already c'
en2 English ZhassanB 2017-06-16 08:05:28 2 Tiny change: ' used build in Buffer' -> ' used built in Buffer'
en1 English ZhassanB 2017-06-16 07:31:22 4560 Initial revision (published)