+1 vote
by
Good day to you, Hubrowites!
I recently started studying at codewars and had a problem with the speed of code execution.
There is a code:
function partsSums(ls) {
ls.reverse();
let a = 0;
arr = [];
let s = ls.length;
for(let i = s; i--;){
for(let j = ls.length; j--;){
a += ls[j];
}
arr.push(a);
ls.pop();
a = 0;
}
arr.push(0);
return ls ? arr : [0];
}
The global test runs for more than 12 seconds. How can I reduce the code execution time? What optimization techniques should I use here? https://www.codewars.com/kata/5ce399e0047a45001c85... - coil reference
by
You don't need to optimize here, but come up with a different algorithm, this one is too much of a head-on.
Read about the complexity of algorithms, calculate what it is you have here come up with another one with less complexity.
by
Maxim Ko , the fastest code is in my answer.
by
Remove the second loop and change the array

2 Answers

0 votes
by
 
Best answer
There was a problem with the speed of code execution

The problem is in the algorithm itself. You don't need to summarize the array elements on each nested iteration, one pass through the array is enough. The code will have to be completely rewritten.
solution
function partsSums(ls) {
const result = new Array(ls.length + 1);
result[ls.length] = 0;

for (let i = ls.length - 1; i > -1; i--) {
result[i] = result[i + 1] + ls[i];
}

return result;
}
0 votes
by
I did this:
function partsSums(ls) {
if(ls.length==0) return [0];
result=ls;
result[i=result.length]=0;
i--;
while(i!==-1)
result[i] = result[i+1]+ls[i--];
return result;
}
Test Results: partsSums Basic tests Random testsCompleted in 2070ms
link PS:
RAX7, ... and mine for ~3000ms ¯\_(ツ)_/¯
squeeze out even cooler?) PS2: RAX7 , By the way, there's the best score - this is also a mutation, but it works in 927.29ms (ours is less than 100ms).
function partsSums(ls) {
ls.unshift(0);
let sum = ls.reduce((p, c) => p + c, 0);
return ls.map(v => sum = sum - v);
}
by
RAX7 , WbICHA This is the average result using Int32Array in the first test from RAX7:
first for: 82.85107421875 ms
second for: 71.656005859375 ms
In any case, mutation wins in speed even against typing, though not by much anymore...
by
xmoonlight I got about twice as much.
by
RAX7 Oh! Thank you. I'll keep that option in mind. And how much is the gain (in %)?
by
WbICHA ,
In the context of this task it is normal, but in general in normal tasks mutations are forbidden.
By whom?)
How much data are you used to working with?
It's not a habit, it's a necessity (it's not web development).
by
RAX7 , Not bad. It's true that such a bit size may not always be enough...
...