Jump to content
Sign in to follow this  
smus

Code optimization

Recommended Posts

How can I optimize this code? It's correct, but performance tests scored just 20%:

function solution(A){
    var al = A.length, c = 0;
    for(var x=0;x<al;x++){
        if(A[x] == 0){
            for(var y=x;y<al;y++){
                if(A[y] == 1){ c++;}
            }
        }
    }
    return c;
}
console.info(solution([0,1,0,1,0,1,0])); //6

Here is the link to the task: https://app.codility.com/demo/results/trainingM8PUJV-HEU/

Edited by smus

Share this post


Link to post
Share on other sites

They want you to only loop through the array once.  How would you do that?  I'm thinking of a solution where you build an array that contains the number of cars passing each other car, and at the end you sum up that array for the total.

Share this post


Link to post
Share on other sites

No, that idea doesn't work either.  This is what I was thinking of:

function solution(A) {
  var res = [], l = A.length, sum = 0, i = 0, j = 0;
  for (i; i < l; i++) {
    if (A[i] == 0) {
      res[i] = 0;
    }
    else {
      res[i] = -1;
      for (j = i; j >= 0; j--) {
        if (res[j] != -1) {
          res[j]++;
        }
      }
    }
  }
  for (i = 0; i < res.length; i++) {
    if (res[i] != -1) {
      sum += res[i];
    }
  }
  return sum;
}

That would also fail a time complexity test, I think it's still O(N^2).  The solution is much more simple, keep track of how many cars you've seen going east, and every time you see one going west you add the number of eastbound cars to the total.

function solution(A) {
  var total = 0, east = 0, i = 0, l = A.length;

  for (i; i < l; i++) {
    if (A[i] == 0) {
      east ++;
    }
    else {
      total += east;
    }
  }

  return total;
}

var max = 100000;
var input = [];
for (var i = 0; i < max; i++) {
  if (Math.random() < 0.5) {
    input[i] = 0;
  }
  else {
    input[i] = 1;
  }
}

console.log(solution([0,1,0,1,1]));
console.log(solution([0,1,0,1,0,1,0]));
var start = new Date();
console.log(solution(input));
var end = new Date();
console.log(end.valueOf() - start.valueOf());

 

Share this post


Link to post
Share on other sites

The other three are because it returned the actual number instead of -1 if the answer is too big.  You can add an if statement for that, my function returns the actual number regardless of how big it is, but that's not what the instructions asked for.

Share this post


Link to post
Share on other sites

Thanks, perfect! So, what I can learn from it, including additional loops significantly increases the script's implementation time. Am I right?

Share this post


Link to post
Share on other sites

If you have nested loops, yes of course it increases.  Look into algorithm time complexity, specifically big-O notation.  The algorithm I posted has linear complexity, O(n), and your original one has exponential complexity, O(n^2).  So, with mine, if the data set increases by 10 times, my algorithm will take roughly 10 times longer, but yours will take roughly 100 times longer.  Determining algorithm complexity is one part of computer science.  A great example of various complexities are the various sorting algorithms.  It's really easy to come up with an exponential sorting algorithm, it's pretty easy to do things the wrong way.  If you look into the various algorithms you'll see attempts to reduce time complexity to something less than exponential time.

  • Thanks 1

Share this post


Link to post
Share on other sites

Where n is the amount of nested loops? According to your explanation, it is better to have several independent loops, than one nested loop:

for(){}

for(){}

for(){}

for(){}

would be faster than:

for(){

  for(){}

}

 

Share this post


Link to post
Share on other sites

Where n is the amount of nested loops?

No, n is the size of the data set.  If you have a single loop over the data set, then the time complexity is linear because the time will grow at about the same rate as the data set grows.  If you have one loop over the data set inside another loop over the data set (or equivalent, as in your case), the time complexity is O(n^2), the time will grow at a much faster rate than the size of the data set.  If you have another nested loop, time complexity is O(n^3) and you're going to be restricted to pretty small data sets if you want to see it finish.

According to your explanation, it is better to have several independent loops, than one nested loop:

Well, the several loops are at least still linear complexity instead of exponential.

  • Thanks 1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×