Faster output via standard out in Java?

Question

In an online judge programming contest problem I am required to output up to 50,000 lines in under 1 second via standard out (in addition to reading in up to 200,000 pairs of integers which I used a buffer for). My logic seems to be correct but I keep getting my submissions turned down for exceeding the 1 second runtime. I stripped down my code logic to just output a constant string and it still exceeds the time limit.

Is there a faster way to output than using System.out.println(String s)for every line of output?

Answer 1

I would use a single System.out.print call (or the least that makes sense which is to be found out via benchmarking) like this:

String str = "line1\nline2\nline3\n ...";
System.out.print(str);

Edit:

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < 500000; i++) {
        sb.append(i).append("\n");
    }
    String str = sb.toString();
    long nt = System.nanoTime();
    System.out.print(str);
    nt = System.nanoTime() - nt;
    System.out.print("\nTime(ms): " + (double)nt / 1000000);

sb.toString() is not a free operation.

The above takes ~650ms on my notebook (500,000 instead of the requested 50,000).

Edit2: with two other tricks, in case the filling time matters:

• construct the StringBuilder with a sufficient capacity

• don't append for every line (the code below appends 200 lines every time, for this it uses a temp sb1); only possible if every line can have the same content. Enjoy.

  long nt = System.nanoTime();
  StringBuilder sb1 = new StringBuilder(400);
  for (int i = 0; i < 200; i++) {
      sb1.append("l").append("\n");
  }
  String strSb1 = sb1.toString();
  
  StringBuilder sb = new StringBuilder(1000000);
  for (int i = 0; i < 2500; i++) {
      sb.append(strSb1);
  }
  
  System.out.print(sb.toString());
  nt = System.nanoTime() - nt;
  System.out.print("\nTime(ms): " + (double)nt / 1000000);
  

~500ms in my case.

Answer 2

As noted above, the solution is to build your String with a StringBuilder and to then print the String returned from the StringBuilder's toString() call. This can and should be testable by you.

Answer 3

It is highly likely you are not using enough buffering. If you writing to System.out it will auto-flush every line so grouping a few lines together before you write can add some buffering. A better approach is to use a proper buffer.

Using a StringBuffer has an inherent cost of growing the buffer.

long start = System.nanoTime();
 StringBuilder sb = new StringBuilder();
for(long i=0;i<50*1000;i++)
  sb.append("Hello World!\n");
System.out.print(sb);
long time = System.nanoTime() - start;
System.err.printf("Took %d ms%n", time/1000000);

prints

Took 30 ms.

However on Linux, if you know stdout is a file you can write to it directly.

long start = System.nanoTime();
String processId = ManagementFactory.getRuntimeMXBean().getName().split("@")[0];
FileOutputStream out = new FileOutputStream("/proc/" + processId + "/fd/1");
BufferedOutputStream bos = new BufferedOutputStream(out);
final byte[] str = "Hello World!\n".getBytes();
for (long i = 0; i < 50 * 1000; i++) {
  bos.write(str);
}
bos.close();
long time = System.nanoTime() - start;
System.err.printf("Took %d ms%n", time/1000000);

prints

Took 9 ms.

However, you do have to be careful how much you optimise the code as you can break the implied rules of the benchmark and not have it accepted. ;)