optimization - converting std input to integer array in java

Question

I want to read each line of input, store the numbers in an int[] array preform some calculations, then move onto my next line of input as fast as possible.

Input (stdin)

2     4  8
15 10               5
12 14 3999 -284                      -71
0 -213 18 4 2
0

This is a pure optimization problem and not entirely good practice in the real world as I'm assuming perfect input. I'm interested in how to improve my current method for taking input from stdin and representing it as an integer array. I have seen methods using scanner where they use a getnextint method, however I've read in multiple places scanner is a lot slower than BufferedReader.

Can this taking in of input step be improved?

Current Method

BufferedReader bufferedInput = new BufferedReader(new InputStreamReader(System.in));
    String line;
    String[] lineArray;
    try{
        // a line with just "0" indicates end of std input
        while((line = bufferedInput.readLine()) != "0"){
            lineArray = line.split("\\s+"); // is "\\s+" the optimized regex
            int arrlength = lineArray.length;
            int[] lineInt = new int[arrlength];
            for(int i = 0; i < arrlength; i++){
                lineInt[i] = Integer.parseInt(lineArray[i]); 
            }
            // Preform some operations on lineInt, then regenerate a new   
            // lineInt with inputs from next line of stdin
        }
    }catch(IOException e){

    }

judging from other questions Difference between parseInt and valueOf in java? parseint seems to be the most efficient method for converting strings to integers1. Any enlightenment would be of great help.

Thank you :)

Edit 1: removed GCD information and 'algorithm' tag

Edit 2: (hopefully) made question more concise, grammatical fix ups

in this line `lineArray = line.split("\\s+")` regex `\s+` is recompiled for each line. To optimize, consider processing a string char-by-char — Alex Salauyou, May 09 '16 at 13:39
I can't tell what you're actually trying to ask. Any GCD algorithm will need to see each parsed integer, so you cannot avoid parsing every integer in the input. Also I'd expect GCD runtime to dominate parsing time, so there's no point worrying about the latter (which is what you're currently worrying about -- right?) — j_random_hacker, May 09 '16 at 13:43
@j_random_hacker in a condescend fashion I'm asking how to get input from stdin in this form (numbers separated by spaces) to an integer array, with as little run time as possible. I thought I would just give a little more background context. Despite the GCD algo dominating runtime I still want my taking in input and displaying output section of my solution to be as quick as possible, note this isn't a real world example it's more an exercise apologies if my jargon is incorrect I'm very new to java and programming in general. — esal284, May 09 '16 at 13:51
It's sometimes good to give a bit of extra context, but here I was confused because you talk about the GCD first, and used the `algorithm` tag, and the GCD will (I'm certain) dominate the running time, so it's hard to tell that you're really just asking about how to efficiently read in an array of integers. I suggest deleting all the GCD-related content and removing the `algorithm` tag (and also not worrying too much about how long this step takes :-) — j_random_hacker, May 09 '16 at 13:59
@j_random_hacker I know it's not great to say thank you, but thank you. I have made my edits and now the problem should make more sense / be more consise i.e stdin(in format indicated) -> int[] as fast as possible. — esal284, May 09 '16 at 14:12
You're welcome :) (BTW I'm a human, and I like to hear a "Thank you", despite whatever the official SO rules say ;) — j_random_hacker, May 09 '16 at 14:16

score 1 · Answer 1 · answered May 09 '16 at 14:24

First of all, I just want out that it is totally pointless optimizing in your particular example.

For your example, most people would agree that the best solution is not the optimal one. Rather the most readable solution is will be the best.

Having said that, if you want the most optimal solution, then don't use Scanner, don't use BufferedReader.readLine(), don't use String.split and don't use Integer.parseInt(...).

Instead read characters one at a time using BufferedReader.read() and parse and convert them to int by hand. You also need to implement your own "extendable array of int" type that behaves like an ArrayList<Integer>.

This is a lot of (unnecessary) work, and many more lines of code to maintain. BAD IDEA ...

score 0 · Answer 2 · edited May 23 '17 at 11:52

I second what Stephen said, the speed of parsing is likely to massively outperform the speed of actual I/O done, therefore improving parsing won't give you much.

Seriously, don't do this unless you've built the whole system, profiled it and found that inefficient parsing is what keeps it from hitting its performance targets.

But strictly just as an exercise, and because the general principle may be useful elsewhere, here's an example of how to parse it straight from a string.

The assumptions are:

You will use a sensible encoding, where the characters 0..9 are consecutive.
The only characters in the stream will be 0..9, minus sign and space.
All the numbers are well-formed.

Another important caveat is that for the sake of simplicity I used ArrayList, which is a bad idea for storing primitives, the overhead of boxing/unboxing probably wipes out all improvement in parsing speed. In the real world I'd use a list variant custom-made for primitives.

public static List<Integer> parse(String s) {
    List<Integer> ret = new ArrayList<Integer>();

    int sign = 1;
    int current = 0;
    boolean inNumber = false;

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c >= '0' && c <= '9') { //we assume a sensible encoding
            current = current * 10 + sign * (c-'0');
            inNumber = true;
        }                       
        else if (c == ' ' && inNumber) {
                ret.add(current);
                current = 0;
                inNumber = false;
                sign = 1;;
        }               
        else if (c == '-') {
            sign = -1;
        }               
    }

    if (inNumber) {
        ret.add(current);
    }

    return ret;
}

optimization - converting std input to integer array in java

2 Answers2