Fast Input & Output
Authors: Benjamin Qi, Nathan Chen
Prerequisites
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.
Fast Input
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 ).
C++
Method 1: freopen
with cin
The slowest method.
973ms
Method 2: freopen
with scanf
Significantly faster.
281ms
Method 3: ifstream
and ofstream
About as fast.
258ms
Method 4: fread
and fwrite
Using FastIO
from here further reduces the runtime.
91ms
Optimizations
Resources | |||
---|---|---|---|
CF | timing various I/O methods |
ios::sync_with_stdio(0)
Resources | |||
---|---|---|---|
CPP | documentation | ||
SO |
From the second resource:
This disables the synchronization between the C and C++ standard streams. By default, all standard streams are synchronized, which in practice allows you to mix C- and C++-style I/O and get sensible and expected results. If you disable the synchronization, then C++ streams are allowed to have their own independent buffers, which makes mixing C- and C++-style I/O an adventure.
Adding this immediately after main()
significantly reduces the runtime of method 1.
299ms
You may also see cin.sync_with_stdio(0)
and ios_base::sync_with_stdio(0)
. These function calls are all equivalent.
Warning!
Make sure that this line comes before taking any input (Source).
If this function is called after I/O has occurred on the standard stream, the behavior is implementation-defined: implementations range from no effect to destroying the read buffer.
Warning!
You can no-longer mix C-style and C++-style I/O (ex. scanf
vs cin
) after including this line. In fact, as freopen
is C-style I/O, it is supposedly prohibited to use freopen
to redirect cin
and cout
if this line is included. But as far as I know, it works properly.
Java
Keep in mind that a Java program that only reads in and outputs a number takes 138ms on USACO.
Method 1 - Scanner
Probably the easiest way to read input in Java, though it is also extremely slow.
3188ms
Method 2 - BufferedReader
and .split()
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 Integer.parseInt(br.readLine())
.
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
.
1209ms
Method 3 - BufferedReader
and StringTokenizer
Notice that StringTokenizer
's .nextToken()
for splitting strings is slightly faster than .split()
.
986ms
As Kattio
is just a wrapper around BufferedReader
and PrintWriter
, it performs similarly. This method is usually fast enough and doesn't require too much typing, so we recommend that you go with this.
Method 4 - BufferedReader
and StreamTokenizer
Apparently this is even faster! Though properly reading in long
s would require additional work (since they are interpreted as double
s by default).
569ms
Method 5 - InputStream
Even faster than BufferedReader
is a custom-written Fast I/O class that reads bytes directly from an InputStream
, similarly as FastIO.h
in the C++ section.
382ms
Python
Faster than the first C++ method! Significantly less if does not need to be stored.
853ms
Fast Output
Focus Problem – read through this problem before continuing!
C++
The following solution has the right time complexity, but it TLEs despite including cin.sync_with_stdio(0)
.
TLE Test 3
Rewriting with scanf
and printf
is an option:
2011ms
But what if we want to stick with cin
and cout
?
Method 1 - Print a Single String
In general, it may be faster to store the answer in a single string
and output 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.
920 ms
Note that the above TLEs on test 5 if cin.sync_with_stdio(0)
is not included.
Also, the change in runtime if we use scanf
and printf
appears to be negligible.
2027 ms
Method 2 - cin.tie(0)
Resources | |||
---|---|---|---|
CPP | documentation | ||
SO |
From the second resource:
This unties
cin
fromcout
. Tied streams ensure that one stream is flushed automatically before each I/O operation on the other stream.By default
cin
is tied tocout
to ensure a sensible user interaction. For example:std::cout << "Enter name:";std::cin >> name;If
cin
andcout
are tied, you can expect the output to be flushed (i.e., visible on the console) before the program prompts input from the user. If you untie the streams, the program might block waiting for the user to enter their name but the "Enter name" message is not yet visible (becausecout
is buffered by default, output is flushed/displayed on the console only on demand or when the buffer is full).So if you untie
cin
fromcout
, you must make sure to flushcout
manually every time you want to display something before expecting input oncin
.
1076 ms
cin.tie(0)->sync_with_stdio(0);
In the above line of code, cin.tie(0)
returns the stream that was previously tied to cin
(cout
). So this is essentially equivalent to:
cin.tie(0), cout.sync_with_stdio(0);
Output streams in C++ (such as cout
and 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
always flushes the output, using \n
instead may avoid unnecessary flushes.
- With
endl
in place of\n
, the above code TLEs on test 3. \n
may also flush the output ifcin.tie(0)
is not present, so removingcin.tie(0)
from the above code also TLEs on test 3.
Warning: cout.tie(0)
You may see some competitive programmers including this line. This doesn't actually do anything since cout
isn't tied to anything ...
Java
In general, it may be faster to store the answer in a single StringBuilder
and output 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.
When printing to the standard output stream in Java, it is faster to use new PrintWriter(System.out)
than System.out
(as all the methods above do). 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 .flush()
or .close()
on the PrintWriter
at the very end of the program in order to write the output.
Module Progress:
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!