Counting athletes whose height is in a given range

Question

Challenge: Sort by growth

Input

• The first line of each query contains one number n (1 ≤ n ≤ 20000) - the number of members in corresponding delegation.
• The second line contains n unsorted integers - the heights of athletes in centimeters. Every height is at least 150 cm, and no greater than 250 cm.
• The third line contains a and b: the lower and upper height limits.

Output

For each query print the count on a separate line.

Time limit: 2 seconds
Memory limit: 256 MiB

My program works correctly, but I have a running time of 3020 ms.

 import java.io.PrintWriter;
 import java.util.Scanner;
 public class OlimpGames {
 public static void main(String[] args) {
 Scanner in = new Scanner(System.in);
 PrintWriter out = new PrintWriter(System.out, true);
 {
 while (in.hasNextInt()) {
 int n = in.nextInt();
 int heigh[] = new int[100];
 for (int i = 0; i < n; i++) {
 heigh[in.nextInt() - 150]++;
 }
 int a = in.nextInt();
 int b = in.nextInt();
 int an = 0;
 for (int i = a - 150; i <= b - 150; i++) {
 an = an + heigh[i];
 }
 System.out.println(an);
 }
 }
 }
}

• Vogel612: I unfortunately do not understand the "For each query..." sentence. The whole question stops making sense that way. Can you clarify?

Answer 1

Your code and algorithm seem pretty optimal for the problem.

A minor nit-pick, the PrintWriter "out" is not being used. (The braces immediately following are unnecessary, but wouldn't affect performance.)

There are only 2 tiny things which might help:

1) In each loop, you're allocating a new int[] array. If you didn't do this, you would need to call Arrays.fill() to zero out the array each time. I doubt there would be much difference as allocations of this type are pretty fast.

2) The bigger possibility is I/O performance on the output. When fine-tuning to meet a time constraint, I/O might make the difference. Instead of calling System.out.println, try using a StringBuilder and appending the output. Then, after the main loop, do a single output operation on the resultant string.

Also, one final tip. The linked problem statement indicates that none are less than 150 or greater than 250. If you get input with 250, you will get an array bounds exception. You need an array of size 101.

Answer 2

First of all, with performance questions, you should always run your program under a profiler tool and find out where it spends most of its time.

Having said that, I guess it's the input from Scanner that's consuming the time, as the other parts of your program look quite efficient. Scanner uses regular expressions internally, so there might be performance potential by replacing it with plain-text input and parsing yourself...

Answer 3

I see no clear algorithmic reason why the time limit is exceeded.

Ralf Kleberhoff points to the probable culprit :

I guess it's the input from Scanner that's consuming the time, as the other parts of your program look quite efficient. Scanner uses regular expressions internally, so there might be performance potential by replacing it with plain-text input and parsing yourself...

To verify this, I tried my hand on some quick-and-dirty number parsing (worthy of ThereIFixedIt.com), and wow, the speed difference:

static int nextInt(InputStream in) throws IOException {
 int ch, retval = 0;
 boolean input = false;
 loop: while ( (ch = in.read()) > 0 ) {
 switch (ch) {
 case '0': case '1': case '2': case '3': case '4':
 case '5': case '6': case '7': case '8': case '9':
 retval = 10*retval + ch - '0';
 if ( !input ) input = true;
 break;
 case ' ': case '\t': case '\r': case '\n': case '\f':
 if ( !input ) continue;
 break loop;
 default:
 throw new IllegalArgumentException();
 }
 }
 return retval;
}
static void readAndQuery(InputStream in, PrintStream out) throws IOException {
 int n;
 while ( (n = nextInt(in)) > 0 ) {
 int height[] = new int[251];
 while ( --n >= 0 ) {
 height[nextInt(in)]++;
 }
 int low = nextInt(in);
 int high = nextInt(in);
 n = 0;
 while ( low <= high ) n += height[low++];
 out.println(n);
 }
}
// java.util.Scanner
$ time java OlimpGames <query-large.txt
real 0m2.578s
user 0m2.670s
sys 0m0.120s
// manual parsing
$ time java OlimpGames <query-large.txt
real 0m0.772s
user 0m0.810s
sys 0m0.050s

You could perhaps squeeze out some extra cycles by guessing that numbers will take up three to four bytes (since they're all between 150 and 250, plus a whitespace char), but the point of the experiment was to check whether we could (削除) do better (削除ここまで) be faster than Scanner, and the answer is yes.