Buffered Reader
From CS315
It has been noted by several UVa puzzler participants that the use of Java's BufferedReader and BufferedWriter consistently improves program run time. Using these classes as alternatives to System.out.println() and Scanner can be tricky for the first user. This wiki attempts to address that issue by suggesting a few implementations and discussing some of the reasons for the runtime differences.
Contents |
Implementations
BufferedReader - Infinite Input
The desired input format for a given puzzler will determine which implementation is most appropriate. The following implementation is best suited for an unspecified number of inputs that will be terminated by the end-of-file signal. This specific example expects input to be given in the form of one integer per line, as was the case in the Sum-of-Four-Primes problem. For puzzlers like 3n+1, which requires multiple numbers of input on a single line, slight modifications to the following example are needed. One possible option would be to use java.util.StringTokenizer to tokenize the different numbers on a single line.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class buffer
{
public static void main(String args[])
{
final BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
try
{
String singleLine = in.readLine();
int singleInt;
while(singleLine != null)
{
singleInt = Integer.parseInt(singleLine); //trusting perfect input
// process singleInt input
singleLine = in.readLine();
}
System.out.println("Done.");
}
catch(IOException e)
{
//do nothing, perfect input promised for puzzlers
}
}
}
- The BufferedReader class, the InputStreamReader that it wraps arround, and the IOException that BufferdReader's readLine() throws are all located in the java.io class and may be imported.
- Because IOException does not extend RunTimeException, the calls to readLine() must be placed within a try/catch block. The catch here is trivial since UVa has promised perfect input.
- It may be initially tempting to try using BufferedReader's ready() method in a similar manner to the hasNext() method found in the Scanner class. This will not work! While the two methods do share similar qualities, the important distinction is that ready() does not block for user input while hasNext() does. This blocking for input is crucial to the Scanner based example provided by Dr. Downing and cannot be mimicked using ready().
- The Behavior of readLine() is such that it will return a null if the end-of-file signal has been transmitted. Therefore the while loop will continue to run until input is finished.
BufferedWriter - Single flush()
The following output implementation is useful for puzzlers like Sum-of-Four-Primes where all output is given after all input has been entered. The following example prints to the console 10 lines of the form "i) Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Vivamus blandit." where "i" represents the line number.
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
public class buffer
{
public static void main(String args[])
{
final BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
String simpleOutput = "Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Vivamus blandit.";
try
{
for(int i=1; i<=10; i++)
{
out.write(i+") " + simpleOutput + "\n");
}
out.flush();
}
catch(IOException e)
{
//do nothing, perfect output promised for puzzlers
}
}
}
- BufferedWriter, the OutputStreamWriter it wraps around, and IOException which may be thrown by BufferedWriter's write() method, all reside in the java.io package and may be imported.
- Because write() may throw an IOException, each call to this method must be placed within a try/catch block. The catch here is trivial since all UVa puzzlers promise perfect output.
- Output does not appear on the screen until the call to flush() is made.
BufferedWriter - Multiple flush()
Some puzzlers, like 3n+1, require output while input is still being given. The following example takes in a line of input and then imediately prints that line to the console. Note that a call to flush() must be made for each line that is output, thereby flushing the output buffer (making it empty) and printing its contents to the screen.
import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
public class buffer
{
public static void main(String args[])
{
final BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
final BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
try
{
String singleLine = in.readLine();
while(singleLine != null)
{
out.write(singleLine+"\n");
out.flush();
singleLine = in.readLine();
}
}
catch(IOException e)
{
//do nothing, perfect I/O promised for puzzlers
}
}
}
- All classes used for this example, as in previous examples, were imported from the java.io package.
- Note that each call to readLine() returns the full line in the input buffer minus the return characters. Therefore, when printing this line back to the console, it is necessary to add the new line character back into the string.
- The speed savings in this example of BufferedWriter is less substantial than in the previous example. The cause for this is explained in further detail bellow.
Concerning Runtime
The following discussion is by no means a definitive all-encompassing comparison.
Scanner vs BufferedReader
When observing the different methods that are available to instances of the Scanner class, we see that several are specific to certain types of input (e.g. nextInt(), nextLong(), etc...). BufferedReader, on the other hand, has far fewer methods and none that really parallel those for specific input types found in Scanner. This distinction is partly responsible for the observable runtime differences between the two classes.
Scanner's methods use a technique known as "pattern-matching" to determine what should be returned by methods like nextInt(). When these methods are called, the input in the buffer is analyzed and an entry of a certain type is sought after. This analysis takes up runtime. BufferedReader, lacking these sorts of methods, is capable of running much faster because this pattern matching is not performed. Scanner does offer more convenience when runtime is less of an issue and not as much is known about the types of input that will be given. However, in the case of UVa puzzlers where perfect I/O is promised, using BufferedReader can be an advantage.
Also, it may be worth noting that both Scanner and BufferedReader use buffered input. Both classes have internal arrays that serve as character buffers.
System.out.println() vs BufferedWriter
As a refresher, recall that "out" is a static instance of PrintStream. Inspection of the PrintStream source reveals that PrintStream actually contains an instance of BufferedWriter internally. The real speed difference comes from the number of calls to BufferedWriter's flush() method.
For every call to println(), a call to flush() is made internally by PrintStream. In cases like the Sum-of-Four-Primes puzzler where output is completely separate from input, this is not necessary and causes slower runtimes. Each call to flush() results in a system-call that writes the contents of the buffer to the console. System-calls are rather slow, so it is useful to minimize these calls when possible.
Therefore, if the particular program will allow for it, it is to your advantage to make the buffer of a BufferedWriter instance as large as you possibly can before flushing and to call flush() as few times as possible. This cannot be done using System.out.println() since the number of calls to flush() cannot be explicitly managed.
Written by Chris Cunningham
