Is there a better way to do partial sums of array items in JavaScript?
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.)
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]
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 + yconst 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-safeconsole .time ("scan")const result = scan (add, 0, data)console .timeEnd ("scan")// scan: 8.07 msconsole .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 -