I wonder if there is a better way of generating a better performing solution for partial sums of an array.
Given an array say x = [ 0, 1, 2, 3, 4, 5 ], I generated sub-arrays of the items, and then computed the sum of each array which gives:
[ 0, 1, 3, 6, 10, 15 ]
So the full code is:
x.map((y,i)=>x.filter((t,j)=>j<=i))
.map(ii=>ii.reduce((x,y)=>x+y,0))
I wonder if flat map or some other array method will have a solution that does not require expanding each subarray.
Much, by keeping a running total:
function* partialSums(iterable) {
let s = 0;
for (const x of iterable) {
s += x;
yield s;
}
}
const x = [0, 1, 2, 3, 4, 5];
console.log(Array.from(partialSums(x)).join(', '));Linear time, online. (You can also produce an array directly; expand below.)
const partialSums = arr => {
let s = 0;
return arr.map(x => s += x);
};
const x = [0, 1, 2, 3, 4, 5];
console.log(partialSums(x).join(', '));yield is such a weak word. Add each item to an array and return it like a man. –
Damp scan and it’s FP because it’s a function. What’s learned: cargo cult FP by shoehorning any task into the magic array functions and avoiding all mutation no matter how local in JavaScript is harmful. –
Thorstein scan, which is implemented in another answer to this very question and which you happen to downvote I guess, as you downvoted at least another answer. –
Looming scan is by replacing s += x with acc = fn(acc, x) in this generator function. –
Thorstein Array.prototype.concat is one of the most harmful methods in JS, since it pretends as if Arrays are persistant data structures. There is a lot justified criticism on FP in JS. So please chime in, justified criticism is always appreciated. –
Looming concat (and equivalently, spread) are harmful ways to pretend one’s being more functional while making complicated solutions to problems that can be solved by creating flatMap or scan, and that local mutations are good ways to implement necessary functions in practical JavaScript… what is it that you take issue with? –
Thorstein You can simply use a for loop with a variable to keep track of the last sum
let x = [ 0, 1, 2, 3, 4, 5 ]
let sum = (arr) => {
let sum = 0
let final = []
for(let i=0; i<arr.length; i++){
sum+= arr[i]
final.push(sum)
}
return final
}
console.log(sum(x))You can also use map:
let x = [0, 1, 2, 3, 4, 5]
let sum = (arr) => {
let sum = 0
return arr.map(current => sum += current )
}
console.log(sum(x))you can also use map, all i wanted to show both the conventional and functional approach, if people feels it's a valid reason to down vote i am happy with it :) –
Headway The flat map won't be useful in your case, because you're not trying to flatten your partial results coming as lists, but we can probably try to resolve your problem in a single reduce:
[0, 1, 2, 3, 4, 5]
.reduce(
([arr, sum], el) => { // We pass along array and running sum
const next = sum + el
return [[...arr, next], next]
},
[[], 0] // We need to seed our reduce with empty array and accumulator for calculating running sum
)[0] // Array containing array and the last sum is returned, so we need to take only the first element
It also iterates the array only once, so it might be a little more performant, than a solution creating slices and then summing them.
Or a version with array.push, which reuses same array:
[0, 1, 2, 3, 4, 5]
.reduce(
([arr, sum], el) => { // We pass along array and running sum
const next = sum + el
arr.push(next)
return [arr, next]
},
[[], 0] // We need to seed our reduce with empty array and accumulator for calculating running sum
)[0]
push, but it will be mutating array, which would make it not purely functional. Have you seen tag functional-programming on question? –
Haaf push is referentially transparent, so it's also fine. Edited my answer to include the second version. –
Haaf Below, scan takes a mapping function f and an initial accumulator r -
const scan = (f, r, [ x, ...xs ]) =>
x === undefined
? [ r ]
: [ r, ...scan (f, f (r, x), xs) ]
const add = (x, y) =>
x + y
const print = (...vs) =>
vs .forEach (v => console .log (v))
const data =
[ 0, 1, 2, 3, 4, 5 ]
print
( scan (add, 0, data)
, scan (Math.max, 3, data)
, scan (add, 0, [])
)
// [ 0, 0, 1, 3, 6, 10, 15 ]
// [ 3, 3, 3, 3, 3, 4, 5 ]
// [ 0 ]If you need a program that does not take an initial accumulator, the first element of the input array can be used instead. This variation is called scan1 -
const scan = (f, r, [ x, ...xs ]) =>
x === undefined
? [ r ]
: [ r, ...scan (f, f (r, x), xs) ]
const scan1 = (f, [ x, ...xs ]) =>
x === undefined
? []
: scan (f, x, xs)
const add = (x, y) =>
x + y
const print = (...vs) =>
vs .forEach (v => console .log (v))
const data =
[ 0, 1, 2, 3, 4, 5 ]
print
( scan1 (add, data)
, scan1 (Math.max, data)
, scan1 (Math.min, data)
, scan1 (add, [])
)
// [ 0, 1, 3, 6, 10, 15 ]
// [ 0, 1, 2, 3, 4, 5 ]
// [ 0, 0, 0, 0, 0, 0 ]
// []Performance optimisations can be made and stack-overflow woes can be remedied, if necessary, all without sacrificing functional style -
const scan = (f, init, xs) =>
loop
( ( r = []
, a = init
, i = 0
) =>
i >= xs.length
? push (a, r)
: recur
( push (a, r)
, f (a, xs[i])
, i + 1
)
)
Now let's run it with a big input -
// BIG data!
const data =
Array .from (Array (10000), (_, x) => x)
// fast and stack-safe
console .time ("scan")
const result = scan (add, 0, data)
console .timeEnd ("scan")
// scan: 8.07 ms
console .log (result)
// [ 0, 0, 1, 3, 6, 10, 15, ..., 49985001 ]
This depends on the following generic functional procedures -
const recur = (...values) =>
({ recur, values })
const loop = f =>
{ let r = f ()
while (r && r.recur === recur)
r = f (...r.values)
return r
}
const push = (x, xs) =>
( xs .push (x)
, xs
)
Expand the snippet below to verify the results in your own browser -
const recur = (...values) =>
({ recur, values })
const loop = f =>
{ let r = f ()
while (r && r.recur === recur)
r = f (...r.values)
return r
}
const push = (x, xs) =>
( xs .push (x)
, xs
)
const scan = (f, init, xs) =>
loop
( ( r = []
, a = init
, i = 0
) =>
i >= xs.length
? push (a, r)
: recur
( push (a, r)
, f (a, xs[i])
, i + 1
)
)
const add = (x, y) =>
x + y
const data =
Array .from (Array (10000), (_, x) => x)
console .time ("scan")
const result = scan (add, 0, data)
console .timeEnd ("scan")
console .log (result)
// [ 0, 0, 1, 3, 6, 10, 15, ..., 49995000 ]scan is good. Implementing scan in JavaScript as if it were Haskell is not good, because it gives you quadratic time complexity and stack overflows on arrays that aren’t even particularly big. –
Thorstein scan. Your comment is appreciated. –
Kine [ r, ...scan (f, f (r, x), xs) ] spread – copy of 0 + 1 + … + n−1 items, quadratic. [ x, ...xs ] destructuring – copy of n−1 + n−2 + … + 0 items, quadratic. Thanks for adding the other version. –
Thorstein O(n*(n+1)/2), which is almost half the complexity of O(n^2), yeah? The optimised revision runs in O(n) though. –
Kine reduce means that we can also choose to implement it on reduce. One way: const scan2 = (f, init, xs) => xs .reduce ( (as, x) => [ ...as, f (as.slice(-1)[0], x) ], [init] ) .slice (1) –
Roid [ r, ...scan (...) ] with [r .concat (...)], assuming that concat is an atomic operation –
Roid reduce; ie, using push from the update, scan2 = (f, init, xs) => push (...xs.reduce (([ r, a ], x) => [ f (r, x), push (r, a) ], [ init, [] ])). I think JavaScript compilers could easily optimize [a, ...b] to [a].concat(b) but the underlying creation of a new array still happens. For significantly large inputs, concat will always perform slower than push in this program. Thanks for the comment :D –
Kine [r, ...s] and [r].concat(s) are the same in that respect. –
Thorstein concat. OTOH, with the speed of either of these, it seems likely that the O(n^2) is likely to be an actual impediment in many reasonable cases... in which case, I vote for clean code. –
Roid [a, ...b] is more like [a].concat(Array.from(b)) because spread argument accepts any iterable. We'd want to look at this with larger array inputs because big inputs are the reason we would optimise in the first place. Thanks everyone for discussion :) –
Kine concat/spread for arrays containing lots of data, because it is incredibly inefficient. But downvoting this answer and waltzing in with the bog-o hammer without prior attempt to settle this isn't the right way. Please note that another user felt encouraged to change this answer extensively, because the discussion provided a breeding ground for it. Anyway, thank you for getting me to reconsider my actions, Scott. –
Looming You just need to add in every step the current value to the previous result, so you could use a simple reduce.
const array = [0, 1, 2, 3, 4, 5, 6];
const sums = array.reduce((acc,current,index) => {
const prev = acc.length ? acc[index-1] : 0;
acc.push(prev + current);
return acc;
},[]);
console.log(sums.toString());If you asking is there a faster or more efficient way then the other answers are sufficient.
However, I'd argue that something similar to your current solution is easier to read and more declarative if we phrase it as a mapping function.
Specifically something like "Map each value to itself plus all the previous values in the array".
You could use a filter, as you have done in your question, but i think a slice is clearer.
const x = [ 0, 1, 2, 3, 4, 5 ];
// A common generic helper function
const sum = (acc, val) => acc + val
const sums = x.map((val, i, self) => val + self.slice(0, i).reduce(sum, 0))
It's possible to use map directly, if you keep an external accumulator variable:
const x = [ 0, 1, 2, 3, 4, 5 ];
let acc = 0;
const prefixSum = x.map(x => acc += x);
console.log(prefixSum);assignment expression, not comfortable with x => acc += x. –
Stcyr One option is to use a single .map which uses .reduce inside to sum up the sliced partial array:
const x = [0, 1, 2, 3, 4, 5];
const sum = (x, y) => x + y;
const partialSums = x.map((_, i, arr) => arr.slice(0, i + 1).reduce(sum));
console.log(partialSums);A way can be to use for each and then slice the arrays to get the elements one by one and then sum them all by array.reduce You can do this like
let x = [0, 1, 2, 3, 4, 5]
let sum = []
x.forEach((_, index) => {
index++;
sum.push(x.slice(0, index).reduce((a, b) => a + b))
})
console.log(sum)We are getting [0] then [0,1] then [0,1,2] then [0,1,2,3] and via [0,1,2].reduce((a, b) => a + b)) we get 3. Just push that to a new array. Which is your answer.
We can go even shorter by doing this. To me, this seems a very optimized solution.
let ar = [0, 1, 2, 3, 4, 5]
let s = 0
let arr = []
ar.forEach((n, i) => arr.push(s += n))
console.log(arr)Or with .map, you can
let ar = [0, 1, 2, 3, 4, 5], s = 0
console.log(ar.map((n, i) => s += n)).map instead of forEach like” But why? –
Thorstein .map’s return value wastes time as well). –
Thorstein map for a push side effect and discards the result. (Well, I guess it’s not pointless, because it means you’re not technically duplicating my answer.) –
Thorstein .map used correctly, i.e. arr.map(x => x * 2) vs. let result = []; arr.forEach(x => { result.push(x * 2) }). let result = []; arr.map(x => { result.push(x * 2) }) is just the worst of both worlds. –
Thorstein .map is faster and that's the only case I'm using it for. I will use .map where I can, to reduce code times a max as possible. Also, anyone can use it however they want right? @Thorstein –
Telemark The simplest answer is a one-liner: if x is [0,1,2,3,4,5]
x.map(i=>s+=i, s=0)
Here is a simple answer using a recursive function.
var array = [ 0, 1, 2, 3, 4, 5 ];
function sumArray(arrayToSum, index){
if(index < arrayToSum.length-1){
arrayToSum[index+1] = arrayToSum[index] + arrayToSum[index+1];
return sumArray(arrayToSum, index+1);
}else
return arrayToSum;
}
sumArray(array, 0);
console.log(array);
© 2022 - 2024 — McMap. All rights reserved.