Optimize calculation of distances between pairs of points

Question

I was trying to solve a challenge. The execution time should not exceed 5s, but for some value my code took longer. I want to know if I can optimize my code for performance.

public class Solution {
    int n;long k;int count=0;
    public static void main(String[] args) {
        new Solution().readInput();


}
public void readInput(){
    try {
        BufferedReader k=new BufferedReader(new InputStreamReader(new FileInputStream("/home/tittanium/NetBeansProjects/HackerRank/src/input.txt")));
        parseNK(k.readLine());
        readAndParse(k.readLine());
        System.out.println(count);
    } catch (IOException ex) {
        Logger.getLogger(Solution.class.getName()).log(Level.SEVERE, null, ex);
    }

}
int cities[];
public void readAndParse(String line){
    int i1=0;
    cities=new int[n];
    StringTokenizer st = new StringTokenizer(line," ");

    while (st.hasMoreElements()) {
         cities[i1]=Integer.parseInt(st.nextToken());
         i1++;
    }
    for(int i=0;i<n;i++){
        final int x=i;
            new Runnable() {
                @Override
                public void run() {
                    for(int j=x;j<n;j++){
                        final int a=cities[x];
                        final int b=cities[j];
                        count = (a>b ? a-b : b-a) == k ? count+1 : count;
                    }
                }
            }.run();
        }
}


public void parseNK(String line){
    n= Integer.parseInt(line.split(" ")[0]);
    k= Integer.parseInt(line.split(" ")[1]);
}


}

This question is trying to solve a problem. I want to know if any changes can be made to make the program run faster. This is what I am trying to complete. challenge

Answer 1

Besides the stylistic issues I mentioned in my other response, your problem is that you are using an O(n²) algorithm. You can easily see that your code is O(n²) because you have two levels of for-loops: the outer i loop taking n iterations, and the inner j loop taking an average of n / 2 iterations.

You should be able do it in O(n) with the help of a data structure. Put all your numbers into a HashSet. Then iterate through the elements, and check whether element + k is also in the set. There are n elements, and each check takes constant time, giving you an O(n) algorithm.

Answer 2

What exactly your code does? It is not obvious, maybe you should name your variables better. Specially count = (a>b ? a-b : b-a) == k ? count+1 : count; What a anb b is? count of what?

Instead of splitting line twice. Split it once and reuse the array. It also reduce count of space literal used.

String[] splittedLine = line.split(" ");
n= Integer.parseInt(splittedLine[0]);
    k= Integer.parseInt(splittedLine[1]);

And you are trying to use thread but you are not starting any. You are just wraping your implementation in Runnable object. See http://docs.oracle.com/javase/tutorial/essential/concurrency/runthread.html for Thread useage examples. Maybe you dont need threads at all, but i cant tell without knowing what exactly you are trying to solve. Running many threads may result into slower code because of switching from one thread to another and their creating take some time.

Answer 3

Before you go for performance, you really need to focus on clarity and correctness.

First of all, what is your code trying to accomplish? After staring at it for five minutes, I'm guessing that it takes a list of locations of n cities along a line, and tries to count the number of pairs of cities that are distance k apart. Stating that in the question would have been appreciated, and stating that in JavaDoc would be even better. Your class name (Solution) is absolutely unhelpful. Your method names readInput() and readAndParse() are downright misleading — they do much more than that!

Another major problem is that you are using threads completely incorrectly. You're nuts to spawn n threads, because:

• There is bookkeeping overhead involved for each thread.
• The bookkeeping and context-switching overhead probably vastly outweighs the amount of real work done by each thread.
• The number of threads should be commensurate with the number of CPU cores available; any more than that just hurts performance.
• The problem you are trying to solve isn't really that parallelizable anyway.

That last point deserves special mention. You are going to get an incorrect result because you don't understand threading. All of your threads want to read and increment count. There will be a race condition. Suppose that two threads both want to increment count at roughly the same time, such that the first thread reads a value for count (say it's 3), then the second thread reads count (also 3), then the first thread increments count (to 4), and finally the second thread also increments count (also to 4). In the end, count will be 4, even though it should have been 5.

To prevent such a race condition, all reads and writes to count would need to be protected by a lock. But then, all the threads would end up queuing in contention for that lock anyway, defeating the purpose of threading in the first place.

In summary, focus on clarity and correctness, and forget about threading.

Edit: Sorry, I mistook your Runnable for a Thread. There's no reason to do (new Runnable() { ... }).run(). You should get rid of the Runnable then, and just execute its code normally.