smus Posted October 23, 2018 Share Posted October 23, 2018 (edited) 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 October 23, 2018 by smus Link to comment Share on other sites More sharing options...
justsomeguy Posted October 23, 2018 Share Posted October 23, 2018 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. Link to comment Share on other sites More sharing options...
justsomeguy Posted October 23, 2018 Share Posted October 23, 2018 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()); Link to comment Share on other sites More sharing options...
smus Posted October 27, 2018 Author Share Posted October 27, 2018 It scored 70% Passed only one more of performance tests (large_extreme: large test with all 1s/0s, length = ~100,000, approx 0.100s) https://app.codility.com/demo/results/training95UXWY-GN8/ Link to comment Share on other sites More sharing options...
justsomeguy Posted October 29, 2018 Share Posted October 29, 2018 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. Link to comment Share on other sites More sharing options...
smus Posted October 30, 2018 Author Share Posted October 30, 2018 Thanks, perfect! So, what I can learn from it, including additional loops significantly increases the script's implementation time. Am I right? Link to comment Share on other sites More sharing options...
justsomeguy Posted October 30, 2018 Share Posted October 30, 2018 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. 1 Link to comment Share on other sites More sharing options...
smus Posted October 31, 2018 Author Share Posted October 31, 2018 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(){} } Link to comment Share on other sites More sharing options...
justsomeguy Posted October 31, 2018 Share Posted October 31, 2018 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. 1 Link to comment Share on other sites More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now