Very Fast Input Scanner

Правка en3, от ZhassanB, 2017-06-16 08:06:09

Hi there! Couple of days ago I was solving problem 796C-Bank Hacking. 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 built 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 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 '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 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.

Теги fastscanner, fastreader, fast input, input reading, large inputs, fast, big inputs, bufferedreader

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский ZhassanB 2017-06-16 08:06:09 6 Tiny change: 'de slice about already c' -> 'de slice already c'
en2 Английский ZhassanB 2017-06-16 08:05:28 2 Tiny change: ' used build in Buffer' -> ' used built in Buffer'
en1 Английский ZhassanB 2017-06-16 07:31:22 4560 Initial revision (published)