Improve the speed of a JavaScript function
For this kind of array maipulations, you better not use build in methods, like slice or reduce, because they are slow in comparison to a for loop, or any other looping approaches.
This approach takes a sinlge loop and uses the index for getting a value of the given array and takes the last sum of the new array.
Some speed tests on Codewars: Sums of Parts:
- 5621 ms with sparse array
sum = []; sum[i] = 0;(the first version of this answer), - 3452 ms with
Array(i + 1).fill(0)and withoutsum[i] = 0;, - 1261 ms with
Array(i + 1)andsum[i] = 0;(find below), - 3733 ms with Icepickle's first attempt.
const partsSums = (ls) => { let i = ls.length; const sum = Array(i + 1); sum[i] = 0; while (i--) sum[i] = sum[i + 1] + ls[i]; return sum; }, ls = [0, 1, 3, 6, 10];console.log(...partsSums(ls));
You can still take a more functional approach but optimise the way you're doing the calculations.
Here is the idea - since you're trying to sum all items, then sum all but the first, then sum all but the second, etc., mathematically equivalent to getting the sum then subtracting from it each number in order and keeping the total.
[sum([41, 42, 43]), sum([42, 43]), sum([43]), sum([])]is the same as:
total = sum([41, 42, 43])[total - 0, total - 0 - 41, total - 0 - 41 - 42, total - 0 - 41 - 42- 43]is the same as:
total = sum([41, 42, 43])[total -= 0, total -= 41, total -= 42, total -= 43]Generalised, this looks like:
total = sum([a1, a2, ..., aN])[total -= 0, total -= a1, total -= a2, ..., total -= aN]Using the trusty Array#reduce we can derive the sum once. Then we can derive the new array using Array.map using ls.map(num => total -= num).
The only problem here is that we get one less item - we don't calculate the initial total -= 0 which has to exist for all items. One way to do it is to append it to the start [0].concat(ls) will create the correct array to map over. However, since we already know what the value there would be, we can skip this step and directly substitute with total (after all the result of total -= 0 is total and leaves total unchanged). So, we can directly use [total].concat(ls.map(num => total -= num)) to start with total and add the rest of the items. to the end.
const ls = [0, 1, 3, 6, 10]const partsSums = (ls) => { let total = ls.reduce((a, b) => a + b, 0); return [total] .concat( ls.map(num => total -= num) );}console.log(partsSums(ls));
Personally, I would just use the previous sum to calculate the next, I don't see any need to re-iterate all the previous sums, so, I would probably go for a basic loop and then reverse the results, like so
function partsSums(ls) { const result = [0]; if (ls.length === 0) { return result; } for (let i = ls.length, q = 0; i--; q++) { result.push(result[q] + ls[i]); } return result.reverse();}or, without reversing, look more like Nina's solution (except for predefining the length of the array)
function partsSums(ls) { const len = ls.length; const result = new Array(len+1); result[len] = 0; for (let i = len; i--;) { result[i] = result[i+1] + ls[i]; } return result;}Both also seem to run faster than Nina's on codewars nodejs engine, in the first part probably because of push, in the second one, probably because the array's length is defined from the start, for more information see this question