wrick's blog

Fastest Scanner in Java
By wrick, history, 7 years ago, In English

In my previous post, I discussed a fast Scanner for Scala.

To benchmark it, I wrote the fastest possible Scanner I could in Java:

package better.files;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.Arrays;

/**
 * Hand built using a char buffer
 */
public class ArrayBufferScanner extends AbstractScanner {
  private char[] buffer = new char[1 << 4];
  private int pos = 0;

  private BufferedReader reader;

  public ArrayBufferScanner(BufferedReader reader) {
    super(reader);
    this.reader = reader;
  }

  @Override
  public boolean hasNext() {
    return pos != -1;
  }

  private void loadBuffer() {
    pos = 0;
    while (true) {
      int i;
      try {
        i = reader.read();
      } catch (IOException e) {
        throw new UncheckedIOException(e);
      }
      if (i == -1) {
        pos = -1;
        break;
      }
      char c = (char) i;
      if (c != ' ' && c != '\n' && c != '\t' && c != '\r' && c != '\f') {
        if (pos == buffer.length) {
          buffer = Arrays.copyOf(buffer, 2 * pos);
        }
        buffer[pos++] = c;
      } else if (pos != 0) {
        break;
      }
    }
  }

  @Override
  public String next() {
    loadBuffer();
    return String.copyValueOf(buffer, 0, pos);
  }

  @Override
  public String nextLine() {
    try {
      return reader.readLine();
    } catch (IOException e) {
      throw new UncheckedIOException(e);
    }
  }

   @Override
  public int nextInt() {
    loadBuffer();
    final int radix = 10;
    int result = 0;
    boolean didRun = false;
    for (int i = buffer[0] == '-' || buffer[0] == '+' ? 1 : 0; i < pos; i++, didRun = true) {
      int digit = buffer[i] - '0';
      checkValidNumber(0 <= digit && digit <= 9);
      result = result * radix + digit;
    }
    checkValidNumber(didRun);
    return buffer[0] == '-' ? -result : result;
  }
  
  private void checkValidNumber(boolean condition) {
    if(!condition) throw new NumberFormatException(String.copyValueOf(buffer, 0, pos));
  }
}

Is this the best I can do?

It is barely faster than Java's StreamTokenizer (NOT StringTokenizer) inspite of being much simpler than it: http://docs.oracle.com/javase/8/docs/api/java/io/StreamTokenizer.html

Java source: https://github.com/pathikrit/better-files/blob/master/benchmarks/src/main/java/better/files/ArrayBufferScanner.java

Other Scanners: https://github.com/pathikrit/better-files/blob/master/benchmarks/src/main/scala/better/files/Scanners.scala

Benchmark results: https://github.com/pathikrit/better-files/tree/master/benchmarks

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can do much better. Just take a look at what happens when you call nextInt() the first time. First the BufferedReader copies input to a buffer, then you copy that data to a new buffer, then you allocate a String object (not ideal if you only want a number) which essentially is just yet another buffer, then you actually parse the input.

If you want to write your own efficient I/O class in Java, then byte[] and System.in.read will be your friends. If you think that's to much of a hassle, well then at least BufferedInputStream is preferable to BufferedReader (at least when it comes to reading integers).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ah, good point — I have not thought about optimizing the nextInt yet... Yes, this is purely an intellectual exercise at this point since it should be fast enough for CodeForces. Btw, what do you think of http://docs.oracle.com/javase/8/docs/api/java/io/DataInputStream.html ? I will include it in my benchmarks next.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I've actually never used it or evaluated its performance. But it does look promising indeed for your purposes.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just posted a version (see updated post) with updated nextInt() — much faster now. Anything else?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Well there's really no point in using a buffer when you use BufferedReader, since it has its own buffer, so you unnecessarily end up doing the same work twice.

      As a reference I include below (more or less) the two classes I use for reading integers (most problems have integers as input) when I wanna make the highscore list on various online judges.

      So feel free to use them as inspiration when you design a more solid class with exception handling etc.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Not related to the post,but worth sharing.

But I'd be careful when using Custom classes to read when the input is large ( especially on SPOJ and UVA). I remember one or two times where encapsulating a BufferedReader and StringTokenizer gave me TLE, yet them alone in the main method gave AC.

Unless you are sure that your scanner is really significant for speed, don't use it when you need every second for your program.

→ Reply
»
7 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Perform the following tasks:

  1. Write a program that calculates the area of a circle, use data type of double.

  2. Write a program to compute distance light travel in 1000 days using long variables.

  3. Write a program that accepts long text and a word. The program shows then number of word repetition and their positions. (hint use while loop and substring method).

  4. Write a program that accepts a number , the program uses for loop to find out if the number is a prime number or not.

  5. Write a program that reads a number "X", then the program calculates the following series : S = 1/2! — 1/3! + 1/4! – 1/5! + ……….. 1/X!, where 4! Is the factorial of 4 and it is equal to 4 *3*2*1>

  6. Write a program that accepts a number and prints the binary code of that number. (hint use loop and mode operator "%".

  7. Write a program for an online music and apps store offers all apps for 3$ each and all songs for 7$ each. The store requires members to prepay any amount of money they wish, and then download as many apps or as many songs accordingly. You are required to write a program that would ask the user for the amount that he/she will pay, then display two messages indicating:

  • the maximum number of apps that can be downloaded, and how much funds will remain in the account after that, if any
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think this tutorial will help you: www.youtube.com/watch?v=dQw4w9WgXcQ

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ffs... this is the third time this happened to me. I think I'm taking you guys too seriously...ugggh

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

some times we just need nextInt , in such cases we can use only System.in and read integer very fast , here is my code that i write it before (3 years ago): http://ideone.com/00avH

i really encourage you to test this (i love this problem , you will learn lots about I/O): http://www.spoj.com/problems/INTEST/

→ Reply