PrevNext

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.

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 101810^{18} (with N=K=105N=K=10^5 and all microcontrollers costing 10810^8).

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
CFtiming various I/O methods

ios::sync_with_stdio(0)

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 NN 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 longs would require additional work (since they are interpreted as doubles 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 PP 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
CPPdocumentation
SO

From the second resource:

This unties cin from cout. Tied streams ensure that one stream is flushed automatically before each I/O operation on the other stream.

By default cin is tied to cout to ensure a sensible user interaction. For example:

std::cout << "Enter name:";
std::cin >> name;

If cin and cout 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 (because cout 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 from cout, you must make sure to flush cout manually every time you want to display something before expecting input on cin.

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 if cin.tie(0) is not present, so removing cin.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!

PrevNext