Competitive Programming with Java : IO

Hello,

in Competitive programming, every problem is in the following form :

we are giving you some input with some form, and we want you to calculate something and write the result in some form .

Which means in every competition or problem you are going to read input from (stdin / file) and write some output (stdout / file) so how can you do that in Java .

Input

I can think of three main ways of reading input, they each have their advantages and weaknesses so let’s have a look at each one of them .

Scanner :

This is the easiest way , Scanner is part of the java.util package, so it’s a class from the standard library, it has multiple constructors mainly Scanner(InputStream) and Scanner(FileInputStream) . the Scanner class is great for small inputs as it’s fast to type and provides a lot of methods to read various types of data, and takes care of tokenizing a string .

	Scanner in = new Scanner(System.in);
	int a = in.nextInt();
	double r = in.nextDouble();
	in.close();

view raw

sc.java

hosted with ❤ by GitHub

on the other hand Scanner’s only weakness is it’s Damn slow, the bigger the input the bigger the impact . with the right amount of input, your algorithm might even not get executed and you will see the dreadful time limit exceeded .

Why Scanner is slow  ?
Scanner uses a Regex matching algorithm to tokenize the read string, sc.nextInt(); is going to try and match [0-9]+ per example plus it has a small buffer size around 1024 bytes .

BufferedReader :

it’s part of the java.io package, it has multiple constructors mainly BufferedReader(Reader). this is a great option for reading large amount of input , because the BufferedReader only reads input from the defined Stream and doesn’t do anything else a part of that, which makes it super-fast plus it has a bigger buffer around 8192 bytes .

	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	String line = in.readLine(); // line is: hello 1 3.0
	String[] data = line.split(" ");
	String word = data[0];
	int number = Integer.parseInt(data[1]);
	double f = Double.parseDouble(data[2]);
	in.close();

view raw

bf.java

hosted with ❤ by GitHub

BufferedReader’s weakness is the parsing part, as you saw in the example i need to tokenize and split the string manually, then parse it to the appropriate type which is not practical in a 2H contest .  😦

FastReader :

This is a costume class you can create (and name it however you like), it uses the best of both worlds : The great Scanner api , and the speed of BufferedReader .

(you can find the complete code in the github repo) .
It uses a class StringTokenizer to split the line read by the internal BufferedReader into tokens and return the next token each time next() is called . then you can do what ever you like with that string , to make it more similar to the Scanner api just define nextInt(), nextLong() ….

This is class is great in contests like ICPC because it’s fast and not that hard to code from scratch .

Lastly if you really need a very fast input you can skip reading with BufferedReader and get your hands dirty and start reading directly from the InputStream (System.in) , with a DataInputStream . this method is really low level . I’m going to explain how it works but it’s not recommended on contests such as ICPC because it’s very painful to code.

Firstly you have a Buffer of bytes which is just an array of size let’s say 4096 .

you keep track of two pointers :

bytesRead : the number of bytes the the DataInputStream read .

bufferPointer : the current byte to read .

the DataInputStream has a method read it takes a byte array and a size and fill it from the stream given in the constructor . and return the number of bytes read, and  that’s how you fill the buffer .

To read a byte you just return the byte at the bufferPointer index .
To read an Integer you need to do manual parsing . (similarly for longs and doubles)

For better understanding refer to the complete code in the github repo .

Benchmarking :

This is a performance comparison done one a text file of size 20M .

Scanner :  6.137s
FastReader :  1.068s
InputReader :  0.950s

Output

Again you have a lot of options but i’m going to talk about 2 :

System.out :

it gives you access to the default PrintStream Object it has a lot of helper methods System.out.println(), System.out.print(), System.out.printf() …
The problem again is efficiency System.out will print every time you tell it to (meaning accessing the console every time you call a print function which is not optimal ) of course if you only got one line of output it doesn’t matter :p . i’m talking huge amount of output .

PrintWriter :

It’s what i use, it’s just a wrapper of System.out, it provides technically the same methods, in addition to a key feature buffering .

Benchmarking :

This is a performance comparison done one a text file of size 20M .

System.out :  4.995s
PrintWriter :  2.885s

That’s it for today’s topic .  😀

• you can Test your code in this practice problem .
•  link to the github repo