# 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```

Edited by smus

##### 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 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;
}
}

}

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 on other sites

It scored 70% Passed only one more of performance tests (large_extreme: large test with all 1s/0s, length = ~100,000, approx 0.100s)

##### 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 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 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.

##### 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 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.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.