Is there a better way to do partial sums of array items in JavaScript?Is there a functional way to init an array in JavaScript ES6?What is the most efficient way to deep clone an object in JavaScript?How do I check if an array includes an object in JavaScript?What's the simplest way to print a Java array?How to insert an item into an array at a specific index (JavaScript)?How do you check if a variable is an array in JavaScript?How do I empty an array in JavaScript?Loop through an array in JavaScriptHow do I remove a particular element from an array in JavaScript?How can I add new array elements at the beginning of an array in Javascript?For-each over an array in JavaScript?
Does ultrasonic bath cleaning damage laboratory volumetric glassware calibration?
What is the olden name for sideburns?
In native German words, is Q always followed by U, as in English?
Reverse of diffraction
When is it ok to add filler to a story?
For people who believe in Jesus and not the devil, what happend in the desert?
How hard is it to sell a home which is currently mortgaged?
Was it really unprofessional of me to leave without asking for a raise first?
Are there any vegetarian astronauts?
How fast can a ship with rotating habitats be accelerated?
Do we or do we not observe (measure) superpositions all the time?
Generate and graph the Recamán Sequence
How can I bypass the confirmation for granting permissions to files or folders?
Coefficients of the characteristic polynomial
What's the safest way to inform a new user of their password on my web site?
Alphabet completion rate
Difference between 'demás' and 'otros'?
Could Sauron have read Tom Bombadil's mind if Tom had held the Palantir?
Can a single server be associated with multiple domains?
Does a centaur PC also count as being mounted?
In the context of a differentiator circuit, what is a “current-sensing resistor”?
What is a macro? Difference between macro and function?
How to convert object fill in to fine lines?
Why transcripts instead of degree certificates?
Is there a better way to do partial sums of array items in JavaScript?
Is there a functional way to init an array in JavaScript ES6?What is the most efficient way to deep clone an object in JavaScript?How do I check if an array includes an object in JavaScript?What's the simplest way to print a Java array?How to insert an item into an array at a specific index (JavaScript)?How do you check if a variable is an array in JavaScript?How do I empty an array in JavaScript?Loop through an array in JavaScriptHow do I remove a particular element from an array in JavaScript?How can I add new array elements at the beginning of an array in Javascript?For-each over an array in JavaScript?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
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.
javascript arrays functional-programming prefix-sum
add a comment |
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.
javascript arrays functional-programming prefix-sum
3
By the way, this is called prefix-sum or scan. Many collections frameworks have it in the standard library, but unfortunately ECMAScript does not.
– Jörg W Mittag
Jun 10 at 0:37
add a comment |
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.
javascript arrays functional-programming prefix-sum
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.
javascript arrays functional-programming prefix-sum
javascript arrays functional-programming prefix-sum
edited Jun 10 at 14:22
qwr
2,5933 gold badges24 silver badges48 bronze badges
2,5933 gold badges24 silver badges48 bronze badges
asked Jun 10 at 0:11
Patrick Francis OmogbemePatrick Francis Omogbeme
1065 bronze badges
1065 bronze badges
3
By the way, this is called prefix-sum or scan. Many collections frameworks have it in the standard library, but unfortunately ECMAScript does not.
– Jörg W Mittag
Jun 10 at 0:37
add a comment |
3
By the way, this is called prefix-sum or scan. Many collections frameworks have it in the standard library, but unfortunately ECMAScript does not.
– Jörg W Mittag
Jun 10 at 0:37
3
3
By the way, this is called prefix-sum or scan. Many collections frameworks have it in the standard library, but unfortunately ECMAScript does not.
– Jörg W Mittag
Jun 10 at 0:37
By the way, this is called prefix-sum or scan. Many collections frameworks have it in the standard library, but unfortunately ECMAScript does not.
– Jörg W Mittag
Jun 10 at 0:37
add a comment |
10 Answers
10
active
oldest
votes
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(', '));
6
Urgh...yield
is such a weak word. Add each item to an array andreturn
it like a man.
– LogicalBranch
Jun 10 at 15:13
1
@LogicalBranch: That wouldn’t be online, so you may as well use the second code snippet then.
– Ry-♦
Jun 10 at 15:14
3
@LogicalBranch Why? Iterators FTW in 2019, no?
– spender
Jun 10 at 19:20
@LogicalBranch Iterators are the way to go when doing partial sums if you have a large array or you only needs up to a certain value. Why do you dislike yield? I know it's not as in your face as return but it is descriptive of what it's doing.
– HSchmale
Jun 11 at 2:28
1
This is a nice imperative answer, However, it doesn't fit a question tagged with functional programming. This is merely a 1:1 alloction of a specific helper function to a very specific problem. Zero generalization, nothing learned.
– bob
Jun 11 at 11:26
|
show 6 more comments
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]
1
This will be equally slow (O(n²)) since it copies the array each time it wants to add something to it.
– Ry-♦
Jun 10 at 15:15
1
@Ry- you can easily replace it withpush
, but it will be mutating array, which would make it not purely functional. Have you seen tagfunctional-programming
on question?
– Krzysztof Atłasik
Jun 10 at 15:48
2
Nothing is purely functional. You own the array. It’s completely fine.
– Ry-♦
Jun 10 at 15:51
1
@Ry- Not really, you can have purely functional methods. But as you mentioned, a version usingpush
is referentially transparent, so it's also fine. Edited my answer to include the second version.
– Krzysztof Atłasik
Jun 10 at 15:54
add a comment |
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 ]
3
scan
is good. Implementingscan
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.
– Ry-♦
Jun 10 at 15:48
2
@Ry-, Thanks but I don't see the quadratic time complexity. The intermediate arrays are definitely wasteful, but the simple programs show precisely what needs to be done. Optimisation with this kind of program is easy so I usually leave them for the end-user who knows their requirements best. An update to the answer shows a stack-safescan
. Your comment is appreciated.
– user633183
Jun 10 at 16:34
1
[ 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.
– Ry-♦
Jun 10 at 16:41
6
Yes, but O(n*(n+1)/2) = O(n²). The “half” is a constant factor.
– Ry-♦
Jun 10 at 16:50
1
@ScottSauyet:[r, ...s]
and[r].concat(s)
are the same in that respect.
– Ry-♦
Jun 10 at 19:07
|
show 16 more comments
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))
That second code snippet looks strikingly familiar, down to the fact that it’s hidden.
– Ry-♦
Jun 10 at 15:15
@Ry- and the above line statesyou 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 :)
– Code Maniac
Jun 10 at 16:13
add a comment |
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());
add a comment |
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))
This describes CertainPerformance’s answer, by the way.
– Ry-♦
Jun 10 at 15:46
The code uses the same approach but I don't think that answer explains the value of the approach. Answers should be more than just the code.
– Steve
Jun 10 at 16:20
add a comment |
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);
Clever trick with assignment expression.
– LiuXiMin
Jun 15 at 8:53
add a comment |
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);
add a comment |
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);
2
This has zero advantages and requires the JIT-compiler to optimize away the recursion, otherwise it could easily overflow the call stack for large arrays. Also it stores the running total to the array and reads it back, instead of keeping it in a variable.
– Peter Cordes
Jun 10 at 18:19
add a comment |
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)
Now what this does is we take a variable and then add the values to it and then simply push that to the array.
“To me, this seems a very optimized solution.” It isn’t. “You can also use.map
instead offorEach
like” But why?
– Ry-♦
Jun 10 at 18:27
Why not?? just for the sake of variety @Ry- Who knows the users is comfortable with any of those?
– weegee
Jun 10 at 18:32
1
There’s a difference in that it pointlessly usesmap
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.)
– Ry-♦
Jun 10 at 19:14
1
No, I just explained why it’s not faster in the way you seem to think that it is. Try a benchmark. Sure, you can use it anyway, and it’ll be bad practice anyway.
– Ry-♦
Jun 10 at 19:50
1
@Ry- okay, I'll accept your approach as I'm a junior and .map returns an array which can also lead to some array waste. Edited my answer
– weegee
Jun 10 at 19:57
|
show 13 more comments
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f56519255%2fis-there-a-better-way-to-do-partial-sums-of-array-items-in-javascript%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
10 Answers
10
active
oldest
votes
10 Answers
10
active
oldest
votes
active
oldest
votes
active
oldest
votes
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(', '));
6
Urgh...yield
is such a weak word. Add each item to an array andreturn
it like a man.
– LogicalBranch
Jun 10 at 15:13
1
@LogicalBranch: That wouldn’t be online, so you may as well use the second code snippet then.
– Ry-♦
Jun 10 at 15:14
3
@LogicalBranch Why? Iterators FTW in 2019, no?
– spender
Jun 10 at 19:20
@LogicalBranch Iterators are the way to go when doing partial sums if you have a large array or you only needs up to a certain value. Why do you dislike yield? I know it's not as in your face as return but it is descriptive of what it's doing.
– HSchmale
Jun 11 at 2:28
1
This is a nice imperative answer, However, it doesn't fit a question tagged with functional programming. This is merely a 1:1 alloction of a specific helper function to a very specific problem. Zero generalization, nothing learned.
– bob
Jun 11 at 11:26
|
show 6 more comments
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(', '));
6
Urgh...yield
is such a weak word. Add each item to an array andreturn
it like a man.
– LogicalBranch
Jun 10 at 15:13
1
@LogicalBranch: That wouldn’t be online, so you may as well use the second code snippet then.
– Ry-♦
Jun 10 at 15:14
3
@LogicalBranch Why? Iterators FTW in 2019, no?
– spender
Jun 10 at 19:20
@LogicalBranch Iterators are the way to go when doing partial sums if you have a large array or you only needs up to a certain value. Why do you dislike yield? I know it's not as in your face as return but it is descriptive of what it's doing.
– HSchmale
Jun 11 at 2:28
1
This is a nice imperative answer, However, it doesn't fit a question tagged with functional programming. This is merely a 1:1 alloction of a specific helper function to a very specific problem. Zero generalization, nothing learned.
– bob
Jun 11 at 11:26
|
show 6 more comments
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(', '));
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(', '));
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(', '));
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(', '));
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(', '));
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(', '));
answered Jun 10 at 0:34
community wiki
Ry-
6
Urgh...yield
is such a weak word. Add each item to an array andreturn
it like a man.
– LogicalBranch
Jun 10 at 15:13
1
@LogicalBranch: That wouldn’t be online, so you may as well use the second code snippet then.
– Ry-♦
Jun 10 at 15:14
3
@LogicalBranch Why? Iterators FTW in 2019, no?
– spender
Jun 10 at 19:20
@LogicalBranch Iterators are the way to go when doing partial sums if you have a large array or you only needs up to a certain value. Why do you dislike yield? I know it's not as in your face as return but it is descriptive of what it's doing.
– HSchmale
Jun 11 at 2:28
1
This is a nice imperative answer, However, it doesn't fit a question tagged with functional programming. This is merely a 1:1 alloction of a specific helper function to a very specific problem. Zero generalization, nothing learned.
– bob
Jun 11 at 11:26
|
show 6 more comments
6
Urgh...yield
is such a weak word. Add each item to an array andreturn
it like a man.
– LogicalBranch
Jun 10 at 15:13
1
@LogicalBranch: That wouldn’t be online, so you may as well use the second code snippet then.
– Ry-♦
Jun 10 at 15:14
3
@LogicalBranch Why? Iterators FTW in 2019, no?
– spender
Jun 10 at 19:20
@LogicalBranch Iterators are the way to go when doing partial sums if you have a large array or you only needs up to a certain value. Why do you dislike yield? I know it's not as in your face as return but it is descriptive of what it's doing.
– HSchmale
Jun 11 at 2:28
1
This is a nice imperative answer, However, it doesn't fit a question tagged with functional programming. This is merely a 1:1 alloction of a specific helper function to a very specific problem. Zero generalization, nothing learned.
– bob
Jun 11 at 11:26
6
6
Urgh...
yield
is such a weak word. Add each item to an array and return
it like a man.– LogicalBranch
Jun 10 at 15:13
Urgh...
yield
is such a weak word. Add each item to an array and return
it like a man.– LogicalBranch
Jun 10 at 15:13
1
1
@LogicalBranch: That wouldn’t be online, so you may as well use the second code snippet then.
– Ry-♦
Jun 10 at 15:14
@LogicalBranch: That wouldn’t be online, so you may as well use the second code snippet then.
– Ry-♦
Jun 10 at 15:14
3
3
@LogicalBranch Why? Iterators FTW in 2019, no?
– spender
Jun 10 at 19:20
@LogicalBranch Why? Iterators FTW in 2019, no?
– spender
Jun 10 at 19:20
@LogicalBranch Iterators are the way to go when doing partial sums if you have a large array or you only needs up to a certain value. Why do you dislike yield? I know it's not as in your face as return but it is descriptive of what it's doing.
– HSchmale
Jun 11 at 2:28
@LogicalBranch Iterators are the way to go when doing partial sums if you have a large array or you only needs up to a certain value. Why do you dislike yield? I know it's not as in your face as return but it is descriptive of what it's doing.
– HSchmale
Jun 11 at 2:28
1
1
This is a nice imperative answer, However, it doesn't fit a question tagged with functional programming. This is merely a 1:1 alloction of a specific helper function to a very specific problem. Zero generalization, nothing learned.
– bob
Jun 11 at 11:26
This is a nice imperative answer, However, it doesn't fit a question tagged with functional programming. This is merely a 1:1 alloction of a specific helper function to a very specific problem. Zero generalization, nothing learned.
– bob
Jun 11 at 11:26
|
show 6 more comments
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]
1
This will be equally slow (O(n²)) since it copies the array each time it wants to add something to it.
– Ry-♦
Jun 10 at 15:15
1
@Ry- you can easily replace it withpush
, but it will be mutating array, which would make it not purely functional. Have you seen tagfunctional-programming
on question?
– Krzysztof Atłasik
Jun 10 at 15:48
2
Nothing is purely functional. You own the array. It’s completely fine.
– Ry-♦
Jun 10 at 15:51
1
@Ry- Not really, you can have purely functional methods. But as you mentioned, a version usingpush
is referentially transparent, so it's also fine. Edited my answer to include the second version.
– Krzysztof Atłasik
Jun 10 at 15:54
add a comment |
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]
1
This will be equally slow (O(n²)) since it copies the array each time it wants to add something to it.
– Ry-♦
Jun 10 at 15:15
1
@Ry- you can easily replace it withpush
, but it will be mutating array, which would make it not purely functional. Have you seen tagfunctional-programming
on question?
– Krzysztof Atłasik
Jun 10 at 15:48
2
Nothing is purely functional. You own the array. It’s completely fine.
– Ry-♦
Jun 10 at 15:51
1
@Ry- Not really, you can have purely functional methods. But as you mentioned, a version usingpush
is referentially transparent, so it's also fine. Edited my answer to include the second version.
– Krzysztof Atłasik
Jun 10 at 15:54
add a comment |
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]
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]
edited Jun 10 at 15:53
answered Jun 10 at 6:56
Krzysztof AtłasikKrzysztof Atłasik
9,2572 gold badges17 silver badges45 bronze badges
9,2572 gold badges17 silver badges45 bronze badges
1
This will be equally slow (O(n²)) since it copies the array each time it wants to add something to it.
– Ry-♦
Jun 10 at 15:15
1
@Ry- you can easily replace it withpush
, but it will be mutating array, which would make it not purely functional. Have you seen tagfunctional-programming
on question?
– Krzysztof Atłasik
Jun 10 at 15:48
2
Nothing is purely functional. You own the array. It’s completely fine.
– Ry-♦
Jun 10 at 15:51
1
@Ry- Not really, you can have purely functional methods. But as you mentioned, a version usingpush
is referentially transparent, so it's also fine. Edited my answer to include the second version.
– Krzysztof Atłasik
Jun 10 at 15:54
add a comment |
1
This will be equally slow (O(n²)) since it copies the array each time it wants to add something to it.
– Ry-♦
Jun 10 at 15:15
1
@Ry- you can easily replace it withpush
, but it will be mutating array, which would make it not purely functional. Have you seen tagfunctional-programming
on question?
– Krzysztof Atłasik
Jun 10 at 15:48
2
Nothing is purely functional. You own the array. It’s completely fine.
– Ry-♦
Jun 10 at 15:51
1
@Ry- Not really, you can have purely functional methods. But as you mentioned, a version usingpush
is referentially transparent, so it's also fine. Edited my answer to include the second version.
– Krzysztof Atłasik
Jun 10 at 15:54
1
1
This will be equally slow (O(n²)) since it copies the array each time it wants to add something to it.
– Ry-♦
Jun 10 at 15:15
This will be equally slow (O(n²)) since it copies the array each time it wants to add something to it.
– Ry-♦
Jun 10 at 15:15
1
1
@Ry- you can easily replace it with
push
, but it will be mutating array, which would make it not purely functional. Have you seen tag functional-programming
on question?– Krzysztof Atłasik
Jun 10 at 15:48
@Ry- you can easily replace it with
push
, but it will be mutating array, which would make it not purely functional. Have you seen tag functional-programming
on question?– Krzysztof Atłasik
Jun 10 at 15:48
2
2
Nothing is purely functional. You own the array. It’s completely fine.
– Ry-♦
Jun 10 at 15:51
Nothing is purely functional. You own the array. It’s completely fine.
– Ry-♦
Jun 10 at 15:51
1
1
@Ry- Not really, you can have purely functional methods. But as you mentioned, a version using
push
is referentially transparent, so it's also fine. Edited my answer to include the second version.– Krzysztof Atłasik
Jun 10 at 15:54
@Ry- Not really, you can have purely functional methods. But as you mentioned, a version using
push
is referentially transparent, so it's also fine. Edited my answer to include the second version.– Krzysztof Atłasik
Jun 10 at 15:54
add a comment |
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 ]
3
scan
is good. Implementingscan
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.
– Ry-♦
Jun 10 at 15:48
2
@Ry-, Thanks but I don't see the quadratic time complexity. The intermediate arrays are definitely wasteful, but the simple programs show precisely what needs to be done. Optimisation with this kind of program is easy so I usually leave them for the end-user who knows their requirements best. An update to the answer shows a stack-safescan
. Your comment is appreciated.
– user633183
Jun 10 at 16:34
1
[ 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.
– Ry-♦
Jun 10 at 16:41
6
Yes, but O(n*(n+1)/2) = O(n²). The “half” is a constant factor.
– Ry-♦
Jun 10 at 16:50
1
@ScottSauyet:[r, ...s]
and[r].concat(s)
are the same in that respect.
– Ry-♦
Jun 10 at 19:07
|
show 16 more comments
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 ]
3
scan
is good. Implementingscan
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.
– Ry-♦
Jun 10 at 15:48
2
@Ry-, Thanks but I don't see the quadratic time complexity. The intermediate arrays are definitely wasteful, but the simple programs show precisely what needs to be done. Optimisation with this kind of program is easy so I usually leave them for the end-user who knows their requirements best. An update to the answer shows a stack-safescan
. Your comment is appreciated.
– user633183
Jun 10 at 16:34
1
[ 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.
– Ry-♦
Jun 10 at 16:41
6
Yes, but O(n*(n+1)/2) = O(n²). The “half” is a constant factor.
– Ry-♦
Jun 10 at 16:50
1
@ScottSauyet:[r, ...s]
and[r].concat(s)
are the same in that respect.
– Ry-♦
Jun 10 at 19:07
|
show 16 more comments
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 ]
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 ]
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 ]
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 ]
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 ]
// []
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 ]
// []
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 ]
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 ]
edited Jun 10 at 19:43
answered Jun 10 at 1:44
user633183user633183
75k21 gold badges147 silver badges190 bronze badges
75k21 gold badges147 silver badges190 bronze badges
3
scan
is good. Implementingscan
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.
– Ry-♦
Jun 10 at 15:48
2
@Ry-, Thanks but I don't see the quadratic time complexity. The intermediate arrays are definitely wasteful, but the simple programs show precisely what needs to be done. Optimisation with this kind of program is easy so I usually leave them for the end-user who knows their requirements best. An update to the answer shows a stack-safescan
. Your comment is appreciated.
– user633183
Jun 10 at 16:34
1
[ 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.
– Ry-♦
Jun 10 at 16:41
6
Yes, but O(n*(n+1)/2) = O(n²). The “half” is a constant factor.
– Ry-♦
Jun 10 at 16:50
1
@ScottSauyet:[r, ...s]
and[r].concat(s)
are the same in that respect.
– Ry-♦
Jun 10 at 19:07
|
show 16 more comments
3
scan
is good. Implementingscan
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.
– Ry-♦
Jun 10 at 15:48
2
@Ry-, Thanks but I don't see the quadratic time complexity. The intermediate arrays are definitely wasteful, but the simple programs show precisely what needs to be done. Optimisation with this kind of program is easy so I usually leave them for the end-user who knows their requirements best. An update to the answer shows a stack-safescan
. Your comment is appreciated.
– user633183
Jun 10 at 16:34
1
[ 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.
– Ry-♦
Jun 10 at 16:41
6
Yes, but O(n*(n+1)/2) = O(n²). The “half” is a constant factor.
– Ry-♦
Jun 10 at 16:50
1
@ScottSauyet:[r, ...s]
and[r].concat(s)
are the same in that respect.
– Ry-♦
Jun 10 at 19:07
3
3
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.– Ry-♦
Jun 10 at 15:48
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.– Ry-♦
Jun 10 at 15:48
2
2
@Ry-, Thanks but I don't see the quadratic time complexity. The intermediate arrays are definitely wasteful, but the simple programs show precisely what needs to be done. Optimisation with this kind of program is easy so I usually leave them for the end-user who knows their requirements best. An update to the answer shows a stack-safe
scan
. Your comment is appreciated.– user633183
Jun 10 at 16:34
@Ry-, Thanks but I don't see the quadratic time complexity. The intermediate arrays are definitely wasteful, but the simple programs show precisely what needs to be done. Optimisation with this kind of program is easy so I usually leave them for the end-user who knows their requirements best. An update to the answer shows a stack-safe
scan
. Your comment is appreciated.– user633183
Jun 10 at 16:34
1
1
[ 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.– Ry-♦
Jun 10 at 16:41
[ 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.– Ry-♦
Jun 10 at 16:41
6
6
Yes, but O(n*(n+1)/2) = O(n²). The “half” is a constant factor.
– Ry-♦
Jun 10 at 16:50
Yes, but O(n*(n+1)/2) = O(n²). The “half” is a constant factor.
– Ry-♦
Jun 10 at 16:50
1
1
@ScottSauyet:
[r, ...s]
and [r].concat(s)
are the same in that respect.– Ry-♦
Jun 10 at 19:07
@ScottSauyet:
[r, ...s]
and [r].concat(s)
are the same in that respect.– Ry-♦
Jun 10 at 19:07
|
show 16 more comments
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))
That second code snippet looks strikingly familiar, down to the fact that it’s hidden.
– Ry-♦
Jun 10 at 15:15
@Ry- and the above line statesyou 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 :)
– Code Maniac
Jun 10 at 16:13
add a comment |
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))
That second code snippet looks strikingly familiar, down to the fact that it’s hidden.
– Ry-♦
Jun 10 at 15:15
@Ry- and the above line statesyou 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 :)
– Code Maniac
Jun 10 at 16:13
add a comment |
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 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))
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))
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))
let x = [0, 1, 2, 3, 4, 5]
let sum = (arr) =>
let sum = 0
return arr.map(current => sum += current )
console.log(sum(x))
let x = [0, 1, 2, 3, 4, 5]
let sum = (arr) =>
let sum = 0
return arr.map(current => sum += current )
console.log(sum(x))
edited Jun 10 at 8:32
Peter Mortensen
14.2k19 gold badges88 silver badges114 bronze badges
14.2k19 gold badges88 silver badges114 bronze badges
answered Jun 10 at 1:46
Code ManiacCode Maniac
16.4k4 gold badges12 silver badges38 bronze badges
16.4k4 gold badges12 silver badges38 bronze badges
That second code snippet looks strikingly familiar, down to the fact that it’s hidden.
– Ry-♦
Jun 10 at 15:15
@Ry- and the above line statesyou 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 :)
– Code Maniac
Jun 10 at 16:13
add a comment |
That second code snippet looks strikingly familiar, down to the fact that it’s hidden.
– Ry-♦
Jun 10 at 15:15
@Ry- and the above line statesyou 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 :)
– Code Maniac
Jun 10 at 16:13
That second code snippet looks strikingly familiar, down to the fact that it’s hidden.
– Ry-♦
Jun 10 at 15:15
That second code snippet looks strikingly familiar, down to the fact that it’s hidden.
– Ry-♦
Jun 10 at 15:15
@Ry- and the above line states
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 :)– Code Maniac
Jun 10 at 16:13
@Ry- and the above line states
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 :)– Code Maniac
Jun 10 at 16:13
add a comment |
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());
add a comment |
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());
add a comment |
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());
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());
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());
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());
answered Jun 10 at 10:04
Pablo LozanoPablo Lozano
7,9221 gold badge25 silver badges49 bronze badges
7,9221 gold badge25 silver badges49 bronze badges
add a comment |
add a comment |
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))
This describes CertainPerformance’s answer, by the way.
– Ry-♦
Jun 10 at 15:46
The code uses the same approach but I don't think that answer explains the value of the approach. Answers should be more than just the code.
– Steve
Jun 10 at 16:20
add a comment |
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))
This describes CertainPerformance’s answer, by the way.
– Ry-♦
Jun 10 at 15:46
The code uses the same approach but I don't think that answer explains the value of the approach. Answers should be more than just the code.
– Steve
Jun 10 at 16:20
add a comment |
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))
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))
answered Jun 10 at 11:29
SteveSteve
7248 silver badges18 bronze badges
7248 silver badges18 bronze badges
This describes CertainPerformance’s answer, by the way.
– Ry-♦
Jun 10 at 15:46
The code uses the same approach but I don't think that answer explains the value of the approach. Answers should be more than just the code.
– Steve
Jun 10 at 16:20
add a comment |
This describes CertainPerformance’s answer, by the way.
– Ry-♦
Jun 10 at 15:46
The code uses the same approach but I don't think that answer explains the value of the approach. Answers should be more than just the code.
– Steve
Jun 10 at 16:20
This describes CertainPerformance’s answer, by the way.
– Ry-♦
Jun 10 at 15:46
This describes CertainPerformance’s answer, by the way.
– Ry-♦
Jun 10 at 15:46
The code uses the same approach but I don't think that answer explains the value of the approach. Answers should be more than just the code.
– Steve
Jun 10 at 16:20
The code uses the same approach but I don't think that answer explains the value of the approach. Answers should be more than just the code.
– Steve
Jun 10 at 16:20
add a comment |
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);
Clever trick with assignment expression.
– LiuXiMin
Jun 15 at 8:53
add a comment |
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);
Clever trick with assignment expression.
– LiuXiMin
Jun 15 at 8:53
add a comment |
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);
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);
const x = [ 0, 1, 2, 3, 4, 5 ];
let acc = 0;
const prefixSum = x.map(x => acc += x);
console.log(prefixSum);
const x = [ 0, 1, 2, 3, 4, 5 ];
let acc = 0;
const prefixSum = x.map(x => acc += x);
console.log(prefixSum);
answered Jun 14 at 7:14
Joe23Joe23
3,6523 gold badges18 silver badges22 bronze badges
3,6523 gold badges18 silver badges22 bronze badges
Clever trick with assignment expression.
– LiuXiMin
Jun 15 at 8:53
add a comment |
Clever trick with assignment expression.
– LiuXiMin
Jun 15 at 8:53
Clever trick with assignment expression.
– LiuXiMin
Jun 15 at 8:53
Clever trick with assignment expression.
– LiuXiMin
Jun 15 at 8:53
add a comment |
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);
add a comment |
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);
add a comment |
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);
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);
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);
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);
answered Jun 10 at 0:14
CertainPerformanceCertainPerformance
115k16 gold badges75 silver badges104 bronze badges
115k16 gold badges75 silver badges104 bronze badges
add a comment |
add a comment |
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);
2
This has zero advantages and requires the JIT-compiler to optimize away the recursion, otherwise it could easily overflow the call stack for large arrays. Also it stores the running total to the array and reads it back, instead of keeping it in a variable.
– Peter Cordes
Jun 10 at 18:19
add a comment |
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);
2
This has zero advantages and requires the JIT-compiler to optimize away the recursion, otherwise it could easily overflow the call stack for large arrays. Also it stores the running total to the array and reads it back, instead of keeping it in a variable.
– Peter Cordes
Jun 10 at 18:19
add a comment |
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);
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);
answered Jun 10 at 16:26
OrionisOrionis
111 silver badge1 bronze badge
111 silver badge1 bronze badge
2
This has zero advantages and requires the JIT-compiler to optimize away the recursion, otherwise it could easily overflow the call stack for large arrays. Also it stores the running total to the array and reads it back, instead of keeping it in a variable.
– Peter Cordes
Jun 10 at 18:19
add a comment |
2
This has zero advantages and requires the JIT-compiler to optimize away the recursion, otherwise it could easily overflow the call stack for large arrays. Also it stores the running total to the array and reads it back, instead of keeping it in a variable.
– Peter Cordes
Jun 10 at 18:19
2
2
This has zero advantages and requires the JIT-compiler to optimize away the recursion, otherwise it could easily overflow the call stack for large arrays. Also it stores the running total to the array and reads it back, instead of keeping it in a variable.
– Peter Cordes
Jun 10 at 18:19
This has zero advantages and requires the JIT-compiler to optimize away the recursion, otherwise it could easily overflow the call stack for large arrays. Also it stores the running total to the array and reads it back, instead of keeping it in a variable.
– Peter Cordes
Jun 10 at 18:19
add a comment |
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)
Now what this does is we take a variable and then add the values to it and then simply push that to the array.
“To me, this seems a very optimized solution.” It isn’t. “You can also use.map
instead offorEach
like” But why?
– Ry-♦
Jun 10 at 18:27
Why not?? just for the sake of variety @Ry- Who knows the users is comfortable with any of those?
– weegee
Jun 10 at 18:32
1
There’s a difference in that it pointlessly usesmap
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.)
– Ry-♦
Jun 10 at 19:14
1
No, I just explained why it’s not faster in the way you seem to think that it is. Try a benchmark. Sure, you can use it anyway, and it’ll be bad practice anyway.
– Ry-♦
Jun 10 at 19:50
1
@Ry- okay, I'll accept your approach as I'm a junior and .map returns an array which can also lead to some array waste. Edited my answer
– weegee
Jun 10 at 19:57
|
show 13 more comments
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)
Now what this does is we take a variable and then add the values to it and then simply push that to the array.
“To me, this seems a very optimized solution.” It isn’t. “You can also use.map
instead offorEach
like” But why?
– Ry-♦
Jun 10 at 18:27
Why not?? just for the sake of variety @Ry- Who knows the users is comfortable with any of those?
– weegee
Jun 10 at 18:32
1
There’s a difference in that it pointlessly usesmap
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.)
– Ry-♦
Jun 10 at 19:14
1
No, I just explained why it’s not faster in the way you seem to think that it is. Try a benchmark. Sure, you can use it anyway, and it’ll be bad practice anyway.
– Ry-♦
Jun 10 at 19:50
1
@Ry- okay, I'll accept your approach as I'm a junior and .map returns an array which can also lead to some array waste. Edited my answer
– weegee
Jun 10 at 19:57
|
show 13 more comments
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)
Now what this does is we take a variable and then add the values to it and then simply push that to the array.
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)
Now what this does is we take a variable and then add the values to it and then simply push that to the array.
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)
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)
let ar = [0, 1, 2, 3, 4, 5]
let s = 0
let arr = []
ar.forEach((n, i) => arr.push(s += n))
console.log(arr)
let ar = [0, 1, 2, 3, 4, 5]
let s = 0
let arr = []
ar.forEach((n, i) => arr.push(s += n))
console.log(arr)
edited Jun 10 at 19:56
answered Jun 10 at 17:55
weegeeweegee
8102 silver badges20 bronze badges
8102 silver badges20 bronze badges
“To me, this seems a very optimized solution.” It isn’t. “You can also use.map
instead offorEach
like” But why?
– Ry-♦
Jun 10 at 18:27
Why not?? just for the sake of variety @Ry- Who knows the users is comfortable with any of those?
– weegee
Jun 10 at 18:32
1
There’s a difference in that it pointlessly usesmap
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.)
– Ry-♦
Jun 10 at 19:14
1
No, I just explained why it’s not faster in the way you seem to think that it is. Try a benchmark. Sure, you can use it anyway, and it’ll be bad practice anyway.
– Ry-♦
Jun 10 at 19:50
1
@Ry- okay, I'll accept your approach as I'm a junior and .map returns an array which can also lead to some array waste. Edited my answer
– weegee
Jun 10 at 19:57
|
show 13 more comments
“To me, this seems a very optimized solution.” It isn’t. “You can also use.map
instead offorEach
like” But why?
– Ry-♦
Jun 10 at 18:27
Why not?? just for the sake of variety @Ry- Who knows the users is comfortable with any of those?
– weegee
Jun 10 at 18:32
1
There’s a difference in that it pointlessly usesmap
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.)
– Ry-♦
Jun 10 at 19:14
1
No, I just explained why it’s not faster in the way you seem to think that it is. Try a benchmark. Sure, you can use it anyway, and it’ll be bad practice anyway.
– Ry-♦
Jun 10 at 19:50
1
@Ry- okay, I'll accept your approach as I'm a junior and .map returns an array which can also lead to some array waste. Edited my answer
– weegee
Jun 10 at 19:57
“To me, this seems a very optimized solution.” It isn’t. “You can also use
.map
instead of forEach
like” But why?– Ry-♦
Jun 10 at 18:27
“To me, this seems a very optimized solution.” It isn’t. “You can also use
.map
instead of forEach
like” But why?– Ry-♦
Jun 10 at 18:27
Why not?? just for the sake of variety @Ry- Who knows the users is comfortable with any of those?
– weegee
Jun 10 at 18:32
Why not?? just for the sake of variety @Ry- Who knows the users is comfortable with any of those?
– weegee
Jun 10 at 18:32
1
1
There’s a difference in that it pointlessly uses
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.)– Ry-♦
Jun 10 at 19:14
There’s a difference in that it pointlessly uses
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.)– Ry-♦
Jun 10 at 19:14
1
1
No, I just explained why it’s not faster in the way you seem to think that it is. Try a benchmark. Sure, you can use it anyway, and it’ll be bad practice anyway.
– Ry-♦
Jun 10 at 19:50
No, I just explained why it’s not faster in the way you seem to think that it is. Try a benchmark. Sure, you can use it anyway, and it’ll be bad practice anyway.
– Ry-♦
Jun 10 at 19:50
1
1
@Ry- okay, I'll accept your approach as I'm a junior and .map returns an array which can also lead to some array waste. Edited my answer
– weegee
Jun 10 at 19:57
@Ry- okay, I'll accept your approach as I'm a junior and .map returns an array which can also lead to some array waste. Edited my answer
– weegee
Jun 10 at 19:57
|
show 13 more comments
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f56519255%2fis-there-a-better-way-to-do-partial-sums-of-array-items-in-javascript%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
By the way, this is called prefix-sum or scan. Many collections frameworks have it in the standard library, but unfortunately ECMAScript does not.
– Jörg W Mittag
Jun 10 at 0:37