# Enormous Input Test - reducing program runtime

This is my solution to SPOJ Problem 442. How can I make this code run faster? What are some techniques that can be used to make this faster? I am getting a Time Limit Exceed Error here.

import java.util.Scanner;

class main{
public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n,k,m=0;
n = input.nextInt();
k = input.nextInt();

for(int c = 0 ; c < n ; c++){
if(input.nextInt() % k == 0) m++;
}

System.out.println(m);
}
}

-
You are expected to be able to process at least 2.5MB of input data per second at runtime. Are you expecting your user to be able to type that much data that fast into the console? Because that sounds impossible to me. –  MrLore Jan 7 '13 at 12:26
How are you getting the Time Limit Exceed Error –  Rhs Jan 7 '13 at 17:10

The main reasons are

• Scanner is pretty slow
• System.in is unbuffered

By using a BufferedReader instead of the Scanner you get it to barely acceptable levels. The following approach runs in roughly 8.2 seconds and get's accepted.

public class Main {
public static void main(String args[]) throws java.io.IOException {
int n, k, m = 0;
n = Integer.parseInt(line0[0]);
k = Integer.parseInt(line0[1]);
for (int c = 0; c < n; c++) {
if (Integer.parseInt(br.readLine()) % k == 0)
m++;
}

System.out.println(m);
}
}


But it's still really slow compared to the top scoring solutions that run in under 2 seconds.

I've got it down to a bit over 2 seconds by reading into a byte[] buffer and doing custom number parsing based on that buffer roughly like the following incomplete piece (which just prints the parsed numbers)

public class Main {
public static void main(String args[]) throws java.io.IOException {
byte[] buffer = new byte[16 * 1024];
int currentNumber = 0;
boolean inNumber = false;
for (int i = 0; i < read; i++) {
char c = (char) buffer[i];
if (c >= '0' && c <= '9') {
inNumber = true;
currentNumber = currentNumber * 10 + (c - '0');
} else if (inNumber) {
inNumber = false;
System.out.println("I've read number: " + currentNumber);
currentNumber = 0;
}
}
}
}
}


See http://ideone.com/lQ4ImB for above code with input

The reason why this is so much faster is basically that there is almost 0 overhead in reading & parsing the input into numbers. BufferedReader in comparison is transforming each line into a String (thus creating a new Object), then parses that String. Above approach allocates no new Objects besides the single byte[] buffer.

-
I wrote last night nearly the same answer. I just want to add an additional idea, which does not fit in a separate answer anymore in my opinion. One could make the reading and checking asynchron. This means, use 2 threads. One is parsing the input and providing integers, the other one is doing the modulo. Use a good block size for the work packet to transfer between the threads and you should have some speed up. (Other improvements involve native methods and unsafe operations, but this will go too far) –  tb- Jan 8 '13 at 11:41
@tb- not sure if multi-threading would improve times since the test is executed on an old single core PIII machine. Native code should not work as well since you can't submit it. Unsafe could indeed prove useful. I also found that optimizing if (number % div == 0) to if (number >= div && number % div == 0) to help a bit since there seem to be enough numbers that the extra instructions are compensated by the faster first check. Also buffer sizes of ~16k-32k seem to perform best. Got it to under 1.9 seconds with stripping every extra operation in the loop I could find –  zapl Jan 8 '13 at 12:59
@tb- it also requires some luck to produce code that is getting optimized better. Some restructuring (adding an e.g. additional final variable before the loop) proved to turn out slower although it should not impact performance. –  zapl Jan 8 '13 at 13:02
yes, optimizations always depends on measurements. Which can not be done because the real data are not accessible. For the multithreading: It is not about using different cores. The plan is to avoid stalls from I/O. Sadly, it would take me too much time to do a carefully tweaked implementation, so it is only an idea which can work in theory. –  tb- Jan 8 '13 at 13:58

According to this question on SO, the issue is with Scanner's nextInt method. Use a BufferedReader, then manually convert the string into an int.

-