I was doing a problem that given an array entry arr
returns the cumulative sum of its elements at subsequent indices... It's this:
Input:
arr= [0, 1, 3, 6, 10]
Output:
arr = [ 20, 20, 19, 16, 10, 0]
because:
ls = [0, 1, 3, 6, 10]
*twenty
ls = [1, 3, 6, 10]
*twenty
ls = [3, 6, 10]
*19
ls = [6, 10]
*16
ls = [10]
*10
ls = []
*0
As I knew that the execution time would be important, I thought of an O(n) solution, iterating for()
faster for these cases than forEach() map() for of
this was my first solution .
function partSums(ls) {
let resp = [0]
let suma = 0
let len= ls.length - 1;
for (let i = len; i >= 0; i--) {
suma += ls[i]
resp.unshift(suma)
}
return resp
}
console.log(partSums([0, 1, 3, 6, 10]))
console.log(partSums([ 20, 19, 16, 10, 0 ]))
I thought that I wouldn't find a way faster than this and that I wouldn't have any problems... however, I didn't pass the speed test. By chance, while testing functions, I did this and to my surprise, I passed the speed test...
function partSums(ls) {
let arr = [0];
ls.reverse().forEach(v => arr.push(arr[arr.length - 1] + v));
return arr.reverse();
}
console.log(partSums([0, 1, 3, 6, 10]))
console.log(partSums([11, 1, 3, 6, 10,14,32,1,3]))
console.log(partSums([11, 1, 3, 0, 1, 3, 6, 10, 6, 10,14,32,1,3]))
I say surprise because for me doing reverse()
2 times and using forEach()
to iterate (slower than for()
) would already be enough to not pass the tests... but this function was significantly faster... another strange thing is that this same function map()
is almost half slower than forEach()
something that is still not clear to me...
Comparing these functions, I concluded that the problem was in the unshift()
!!!
function partsSums(ls) {
let resp = [0]
let acum = 0
let len= ls.length - 1
for (let i = len; i >= 0; i--) {
acum += ls[i]
resp.push(acum)
}
return resp.reverse()
}
console.log(partsSums([0, 1, 3, 6, 10]));
So my question is how is it possible that he unshift()
is so much more expensive in time than push()
him... that he reverse()
(which for me had to do something similar to for()
changing indices) is so fast... and how is it also possible that forEach() is almost as fast as for()
him and faster than him map()
?
Initially I would like to point out that you could save yourself the last
reverse
, if instead of doingpush
you were adding the results inresp[i]
Example:
Now in response to:
If we take into account what it
unshift(value)
means to add an element to the beginning of the array, i.e. all previously added elements have to be moved fromn
ton+1
, then it makes sense that it would be slower to dounshift
thanpush
( add to end )And in response to:
This depends on the implementation of each method in each browser.
For example,
map
if we look at supolyfill
we could say that it is slower than afor
, because in this one: