7
$\begingroup$

Please consider the following list data. I was trying to accumulate data until the result turns positive the first time and finally found an approach. Maybe it's useful to others and maybe there are other (more efficient) approaches:

data={-1050, 50, 1001, 1950, 1950, 1950, 525, 0};

The same what Accumulate does can be done by FoldList:

Rest@FoldList[Plus, 0, data] == Rest@FoldList[#1 + #2 &, 0, data] == Accumulate@data
(*True*)

Now, one can add constraints to FoldList. For my problem I had to write:

Rest[FoldList[If[#1 + #2 < #2, #1 + #2, #2] &, 0, #]]&@data
(*{-1050, -1000, 1, 1950, 1950, 1950, 525, 0}*)

Question

How can this be improved, either in terms of speed or elegance?

$\endgroup$
8
  • 1
    $\begingroup$ I'd suggest you add "How can this be improved, either in terms of speed or elegance" or something like that at the end. Then it's a question! $\endgroup$
    – acl
    Nov 1, 2012 at 21:44
  • $\begingroup$ @acl I added your advice. $\endgroup$
    – John
    Nov 1, 2012 at 21:47
  • $\begingroup$ At the very least, you should have started with simplifying the two-argument function: If[#1 < 0, #1, 0] + #2 &. The versions using Boole[] or UnitStep[] seemed a bit slower in my tests; someone might want to do more testing on those. $\endgroup$ Nov 2, 2012 at 1:29
  • $\begingroup$ Do you want your output to stop at the point the accumulation goes positive? The answers provide some examples that do this and some that don't. Might be useful to clarify. You could use something like LengthWhile or TakeWhile to obtain that output from the full list. $\endgroup$ Nov 2, 2012 at 6:50
  • $\begingroup$ @MikeHoneychurch The code-line with FoldList is only there to describe how I got to the last code-line. The most crucial point to me was to formulate an alternative to Accumulate with the addition of implementing conditions. $\endgroup$
    – John
    Nov 2, 2012 at 15:06

3 Answers 3

3
$\begingroup$

Here is another way:

With[{acc = Accumulate@data}, acc[[;; -#]] ~Join~ data[[-# + 1 ;;]] &@Count[acc, _?Positive]]
(* {-1050, -1000, 1, 1950, 1950, 1950, 525, 0} *)

You can also use Tr@Boole@Thread[acc > 0]] instead of Count[...] or if you want ≥0, then you can use Tr@UnitStep[acc].

$\endgroup$
7
  • $\begingroup$ HeavisideTheta[0] is undefined, so this has problems if the total reaches zero. $\endgroup$ Nov 1, 2012 at 22:33
  • $\begingroup$ @SimonWoods Good point. Fixed now :) $\endgroup$
    – rm -rf
    Nov 1, 2012 at 23:03
  • 1
    $\begingroup$ UnitStep doesn't have that problem $\endgroup$
    – Rojo
    Nov 2, 2012 at 0:28
  • $\begingroup$ @Rojo Yep, I mentioned it in my answer, but note that UnitStep is equivalent to ≥0, whereas OP only mentioned >0. $\endgroup$
    – rm -rf
    Nov 2, 2012 at 3:00
  • 1
    $\begingroup$ Also I think this approach would only work for data whose accumulation doesn't go negative after getting positive for the first time, right? $\endgroup$
    – Rojo
    Nov 2, 2012 at 3:24
2
$\begingroup$

You could also do

Join[#, data[[Length@# + 1 ;;]]] &@
 Reap[Fold[If[NonPositive@#1, Sow[#1 + #2], Break[Null, Fold]] &, 0, 
    data]][[-1, 1]]

{-1050, -1000, 1, 1950, 1950, 1950, 525, 0}

$\endgroup$
2
$\begingroup$

Perhaps if you like recursion this might seem more elegant, it certainly doesn't win on speed.

Recursive

NestWhile[{First@#~Plus~#[[2, 1]], Rest@#[[2]]} &, {0, data}, 
 NonPositive@First@# && Length@#[[2]] >= 1 &]

{1, {1950, 1950, 1950, 525, 0}}

Timing:

data = RandomInteger[{-1000, 10}, 100000];

AbsoluteTiming[
 NestWhile[{First@#~Plus~#[[2, 1]], Rest@#[[2]]} &, {0, data}, 
   NonPositive@First@# && Length@#[[2]] >= 1 &];]

{1.005087, Null}

rm -rf

AbsoluteTiming[
 With[{acc=Accumulate@data},acc[[;; -#]]~Join~data[[-# + 1 ;;]] &@Count[acc,_?Positive]];]

{0.024329, Null}

Rojo

AbsoluteTiming[
 Join[#, data[[Length@# + 1 ;;]]] &@
   Reap[Fold[If[NonPositive@#1, Sow[#1 + #2], Break[Null, Fold]] &, 0,
       data]][[-1, 1]];]

{0.104658, Null}

$\endgroup$
2
  • $\begingroup$ The second method is very fast but is correct only assuming the cumulative sums remain positive forever after they first turn positive. $\endgroup$
    – whuber
    Nov 29, 2012 at 21:36
  • 1
    $\begingroup$ @whuber Yes indeed, thank you for noting that :) The second method, I think, came from an earlier version of the answer from rm -rf which has now been updated in light of comments from Simon Woods which I'd missed. I'll update my answer accordingly. $\endgroup$ Nov 30, 2012 at 9:56

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.