Check divisibility of each line in a large dataset

Question

I have solved this assignment in online coding community, and it has run successfully. But it's showing 12.09s of execution.

How could this be optimized ?

The purpose of this problem is to verify whether the method you are using to read input data is sufficiently fast to handle problems branded with the enormous Input/Output warning. You are expected to be able to process at least 2.5MB of input data per second at runtime.

Input

The input begins with two positive integers n k (n, k<=10^7). The next n lines of input contain one positive integer t(i), not greater than 10^9, each.

Output

Write a single integer to output, denoting how many integers t(i) are divisible by k

import java.util.*;
import java.io.*;
class InputTest{
public static void main(String args[]) throws Exception{
 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 String arr[]=br.readLine().split(" ");
 int n=Integer.parseInt(arr[0]);
 int k=Integer.parseInt(arr[1]);
 int count=0;
 if(n<=0 || k<=0 || k>Math.pow(10,7)){
 throw new Exception();
 }
 else{
 for(int i=0;i<n;i++){
 int m=Integer.parseInt(br.readLine());
 if(m>Math.pow(10,9))
 throw new Exception();
 if(m%k==0)
 count++;
 }
 System.out.println(count);
 }
}
}

Answer 1

class InputTest{

Spacing.

public static void main(String args[]) throws Exception{

Again. There should be a space before each "{".

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

You're using a platform dependent encoding (which is actually nearly always wrong). There are chances that it's UTF-8 and it probably takes quite some time.

Nearly any encoding would do, and e.g., LATIN-1 should be faster as it converts one byte to one char, which is way simpler than UTF-8.

But even faster would be no encoding at all. The whole input can be easily read directly from bytes.

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

Spaces are inexpensive, use them! No more comments on formatting.

if(m>Math.pow(10,9))

Gotcha! Why are you exercising such an expensive operation every time? And why do you wonder that it's slow? Maybe the JIT may be able to optimize it away, but

1. You could simply 1e9 and get rid of the computation.
2. You could simply write 10000000 or (since Java 7) even 10_000_000 and have an integer as it should be.

3. But you surely should define a constant instead. The it doesn't matter how complicated the computation is as it gets done just once.

   throw new Exception();

That's ugly. Exception is too unspecific and there's no message there. What about a

throw new RuntimeException(String.format("Invalid (k, n) = (%s, %s)", k, n));

Or would maybe

assert n > 0 : n;
assert k > 0 : k;
assert k <= 10_000_000 : k;

do?

---

So again, if you want to speed it up,

• remove the obvious inefficiency
• don't use strings
• read the file in as a byte[]
• parse numbers from it manually

---

For really big inputs, it could make sense to avoid both the conversion to int and the modulo computation by creating a data structure working directly with the input byte[]. But this is rather complicated , surely not for everyone.

• Heslacher: Is there a difference in your post about the BufferedReader regarding the encoding which I don't see ?
• maaartinus: @Heslacher I wrote nothing concerning this, was just citing OP's code. A different encoding could be specified via the InputStreamReader constructor (rather then BufferedReader). But a bigger speedup comes from avoiding it altogether.

Answer 2

With most things covered, here are a few:

• Main should not be throwing an exception. Instead Log it or make a function call which throws the exception and catch it in main with proper logs. https://stackoverflow.com/questions/17629321/throwing-exception-in-main-method
• Do we really want to exit if you get a number beyond the range. Instead, we could log it, ignore it and just continue with the rest. Your call.
• Can arr be null or with size less than the array size you require. Have a validation there.
• Be specific with your imports and remove unused ones. https://stackoverflow.com/questions/8401523/difference-between-complete-package-import-and-specified-class-import-java
• Be specific with your exception be it while throwing or catching. http://www.javaworld.com/article/2073800/testing-debugging/beware-the-dangers-of-generic-exceptions.html

• Aniruddha Paul: :-Yes I think we need to let the program finish without any computation if the i/p is beyond the range and regarding your 4th point i think importing the required class will be faster comparison to importing the package.m i ri8?
• thepace: Just a compile time overhead in finding the correct class.