2
$\begingroup$

I want to find an efficient method to generalize how the function Accumulate works.

An example should make it clear:

x=Range[10];
Accumulate[x]

Out[36]= {1, 3, 6, 10, 15, 21, 28, 36, 45, 55}

which can be replicated by:

Plus @@@ Table[Take[x, i], {i, Length@x}]

Out[35]= {1, 3, 6, 10, 15, 21, 28, 36, 45, 55}

More generally, for any function f, what I want is a more efficient and elegant way of doing this:

 f @@@ Table[Take[x, i], {i, Length@x}]

Out[34]= {f[1], f[1, 2], f[1, 2, 3], f[1, 2, 3, 4], f[1, 2, 3, 4, 5], 
 f[1, 2, 3, 4, 5, 6], f[1, 2, 3, 4, 5, 6, 7], 
 f[1, 2, 3, 4, 5, 6, 7, 8], f[1, 2, 3, 4, 5, 6, 7, 8, 9], 
 f[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]}

It looks like something that could be handled with FoldList or ArrayFilter, but I don't see how: I want f[1,2] not f[f[1],2]. That happens to work for f = Plus, but it won't necessarily work for other functions.

For example, suppose we want to produce a list of standardized values, but we only want to use the prior data to calculate the mean and standard deviation.

RepeatedTiming[
 Prepend[Last /@ 
    Standardize @@@ Table[{Take[x, i]}, {i, 2, Length@x}], 0] // N]

Out[60]= {0.00105957, {0., 0.707107, 1., 1.1619, 1.26491, 1.33631, 
  1.38873, 1.42887, 1.46059, 1.4863}}

or

RepeatedTiming[
 Prepend[Last /@ 
    Standardize @@@ List /@ Rest@Rest@FoldList[Append, {}, x] // N, 0]]

Out[84]= {0.00106662, {0, 0.707107, 1., 1.1619, 1.26491, 1.33631, 
  1.38873, 1.42887, 1.46059, 1.4863}}

or

RepeatedTiming[
 Prepend[Last /@ 
    Standardize @@@ List /@ Reverse@NestList[Most, x, Length@x - 2] //
    N, 0]]

Out[109]= {0.00105479, {0, 0.707107, 1., 1.1619, 1.26491, 1.33631, 
  1.38873, 1.42887, 1.46059, 1.4863}}

Can anyone improve on the syntax and/or speed of these expressions?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
4
$\begingroup$

Edit

alist = Range[10];
ReplaceList[alist, {b__, c___} :> {b}]

{{1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}, {1, 2, 3, 4, 5}, {1, 2, 3, 4,
5, 6}, {1, 2, 3, 4, 5, 6, 7}, {1, 2, 3, 4, 5, 6, 7, 8}, {1, 2, 3, 4,
5, 6, 7, 8, 9}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}

AbsoluteTiming[(f @@@ ReplaceList[alist, {b__, c___} :> {b}])

> {0.0000941792, {f[1], f[1, 2], f[1, 2, 3], f[1, 2, 3, 4],    f[1, 2,
> 3, 4, 5], f[1, 2, 3, 4, 5, 6], f[1, 2, 3, 4, 5, 6, 7],    f[1, 2, 3,
> 4, 5, 6, 7, 8], f[1, 2, 3, 4, 5, 6, 7, 8, 9],    f[1, 2, 3, 4, 5, 6,
> 7, 8, 9, 10]}}

This timing will worsen depending on what the function is doing and the length of the list.

More succinctly and elegantly, the following generates the same output:

ReplaceList[alist, {b__, c___} :> f@b]

Original

x = Range[10];
Accumulate[x] // RepeatedTiming

{4.96791*10^-7, {1, 3, 6, 10, 15, 21, 28, 36, 45, 55}}

FoldList[#1 + #2 &, x] // RepeatedTiming

{4.13332*10^-6, {1, 3, 6, 10, 15, 21, 28, 36, 45, 55}}

Using Sow:

x = Range[10];

Last@Reap@Scan[Sow[f @@ #] &, Range[x]] // RepeatedTiming

{0.0000291362, {{f[1], f[1, 2], f[1, 2, 3], f[1, 2, 3, 4], f[1, 2, 3, 4, 5], f[1, 2, 3, 4, 5, 6], f[1, 2, 3, 4, 5, 6, 7], f[1, 2, 3, 4, 5, 6, 7, 8], f[1, 2, 3, 4, 5, 6, 7, 8, 9], f[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]}}}

Improve this answer
$\endgroup$
8
  • $\begingroup$ RepeatedTiming[FoldList[Plus, 0, x]] Out[38]= {2.63173*10^-6, {0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55}} $\endgroup$
    – MMAUser
    Commented Oct 21, 2022 at 10:06
  • $\begingroup$ RepeatedTiming[Plus @@@ Table[Take[x, i], {i, Length@x}]] Out[39]= {0.0000197784, {1, 3, 6, 10, 15, 21, 28, 36, 45, 55}} $\endgroup$
    – MMAUser
    Commented Oct 21, 2022 at 10:07
  • $\begingroup$ So FoldList is faster $\endgroup$
    – MMAUser
    Commented Oct 21, 2022 at 10:09
  • $\begingroup$ Minor changes can create differences in performance while using Mathematica. It depends on your application. $\endgroup$
    – Syed
    Commented Oct 21, 2022 at 10:11
  • $\begingroup$ Hi, there is something I could not understand. I compared the timing of your ReplaceList method with the timing of the NestList method in my answer. Using a testlist=Range[10^4] and prior to using f@@@ (so just the nested list), the NestList method was 6 times faster than using ReplaceList. However, once f@@@ is used the ReplaceList method was 2 times faster. It seems that somehow, although the nested lists look the same, they are internally coded differently. To verify I used On["Packing"] to check for array unpacking. I found that f@@@ unpacks each list one at a time with $\endgroup$
    – userrandrand
    Commented Oct 22, 2022 at 2:19
4
$\begingroup$ 
n = 5;
testlist = Range[n];
f @@@ Reverse@NestList[Most, #, Length@# - 1] &@testlist

{f[1], f[1, 2], f[1, 2, 3], f[1, 2, 3, 4], f[1, 2, 3, 4, 5]}

Or

f @@@ Reverse@NestWhileList[Most, testlist, Length@# > 1 &]

Or with a symbolic function that does not evaluate to anything (for the fun of playing with Slot and using Accumulate)

Function[Evaluate[ReplaceAll[Plus -> Sequence][
f /@ Accumulate[Slot /@ Range[Length@testlist]]]]] @@ testlist
Improve this answer
$\endgroup$
0
$\begingroup$

Proposal 1:

f@@@Rest[FoldList[Append,{},{a,b,c,d}]]
(* {f[a],f[a,b],f[a,b,c],f[a,b,c,d]} *)

Proposal 2:

Rest[FoldList[Append,f[],{a,b,c,d}]]
(* {f[a],f[a,b],f[a,b,c],f[a,b,c,d]} *)

But proposal 2 will not work if f evaluates to something.

Since OP mentions standardization as an example, I think that is a case where I would not use this kind of function, instead something like

runningMean[x_]:=Accumulate[x]/Range[1,Length[x]];
runningVar[x_]:=(runningMean[x^2]-runningMean[x]^2)*Join[{1},Range[2,Length[x]]/Range[1,Length[x]-1]];
runningStandardize[x_]:=Join[{0},(Rest[x]-Rest[runningMean[x]])/Sqrt[Rest[runningVar[x]]]];

For long lists this will be faster than the approach suggested in the post.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ I wouldn't class that as being any more "elegant" that my own solution, but is it any faster, I wonder? $\endgroup$
    – MMAUser
    Commented Oct 21, 2022 at 9:45
  • $\begingroup$ As long as f is not specified, one is just building up a big expression. What does efficiency mean then? What do you want to apply this to, lists of numbers? What are the f you have in mind? $\endgroup$
    – user293787
    Commented Oct 21, 2022 at 9:50
  • $\begingroup$ I just find it strange that there isn't a generalized way to replicate the functionality of Accumulate for functions other than Plus. A good example of where this would be useful is e.g. Standardize. You want to generate a list of standardized values using the mean and variance of the prior data (not for the entire list). $\endgroup$
    – MMAUser
    Commented Oct 21, 2022 at 10:11
  • $\begingroup$ Something like Prepend[Last /@ Standardize@@@Table[Take[x,i],{i,2,Length@x}],0] $\endgroup$
    – MMAUser
    Commented Oct 21, 2022 at 10:15
  • 1
    $\begingroup$ @MMAUser Rest[FoldList[Append,f[],{a,b,c,d}]] is the most general way to do this, but depending on the function there are better ways. The thing about Plus is that it's special in that it's associative (i.e., Plus[Plus[a,b], c] === Plus[a,b,c]). That's what makes Accumulate more efficient than a fold with an arbitrary function. To make something like this work with something like averages, you need a special function that can update running averages. $\endgroup$
    – Sjoerd Smit
    Commented Oct 21, 2022 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.