Fast Input & Output
Authors: Benjamin Qi, Nathan Chen
Speeding up I/O speeds can make a substantial difference in problems with large inputs.
Generally, input and output speed isn't an issue. However, some platinum tasks have relatively large input files. The USACO Instructions Page briefly mentions some ways of speeding up I/O; let's check that these actually make a difference.
Focus Problem – read through this problem before continuing!
The largest USACO input file we know of is test case 11 of Robotic Cow Herd (10.3 megabytes). The answer to this test case is (with and all microcontrollers costing ).
The slowest method.
About as fast.
If we use FastIO from here then the runtime is further reduced.
Adding this immediately after
main() significantly reduces the runtime of method 1.
You may see
cin.sync_with_stdio(0); used in place of
ios_base::sync_with_stdio(0); but they should have the same effect.
Keep in mind that a Java program that only reads in and outputs a number takes 138ms on USACO.
Scanner is probably the easiest way to read input in Java, though it is also extremely slow.
A common alternative to reading input for programming contests is
BufferedReader, which reads faster from a file than
BufferedReader reads line-by-line with the
.readLine() method, which returns a string. Methods like
Integer.parseInt() are used to convert strings into primitives, and they can directly convert a line into a number, like in
Reading input is more complicated when multiple, space-separated values are placed in a single line. In order to individually read the values in each line, the programmer usually uses the
.split() method in
String or the
StringTokenizer. Notice that
StringTokenizer for splitting strings is slightly faster than
StreamTokenizer is even faster!
Reading input with
Reading input with
Reading input with
Faster methods of reading input exist too - Even faster than
BufferedReader is a custom-written Fast I/O class that uses
InputStream. Note that this custom class is similar to the custom-written
FastIO.h in the C++ section, as both read input through a byte buffer. Despite the name of the class being "FastIO," it only reads input.
The most realistic input method to implement in contest is
BufferedReader, as it is relatively fast for the amount of code necessary.
Faster than the first C++ method! Significantly less if does not need to be stored.
In general, it may be faster to store the answer all in a single
string (C++) or
StringBuilder (Java) and outputting it with a single function call. This method avoids the overhead of calling an output method many times, especially if the output is generated in many parts.
The CF blog mentioned above notes that when printing many lines in C++, it may be faster to use the newline character
\n in place of
endl. Output streams in C++ (such as
ofstream) are buffered, meaning that they don't immediately print their output, but store some of it. At some point, the buffer's contents are written (i.e. "flushed") to the output device (e.g the standard output stream or a file). Buffering the output helps with efficiency if accessing the output device (like a file) is slow. Because
endl flushes the output, it may be faster to use
\n instead and avoid unnecessary flushes.
When printing to the standard output stream in Java, it is faster to use
new PrintWriter(System.out) than
System.out. The syntax for
PrintWriter is equivalent to that of
System.out so it should be easy to use. The only difference is that one has to call
.close() on the
PrintWriter at the very end of the program in order to write the output.
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!
Give Us Feedback on Fast Input & Output!
Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.