Faster "stuttering" accumulate?

Question

Given some list of arbitrary precision numbers, e.g. (actual lists are 1M+ elements long):

test={0, 2, 2, 47839283, 2, 0, 0, 2, 0, 1, 2, 0}

I need to accumulate the list, but where a specified element value is treated as "clear", that is, the accumulation is reset to zero at that point in the list and continues.

With the above example, using zero as the "clear", the result would be e.g.:

{0, 2, 4, 47839287, 47839289, 0, 0, 2, 0, 1, 3, 0}

I'm using

Function[{lst, clr}, FoldList[If[#2 == clr, 0, +##] &, lst[[1]], Rest@lst]][test, 0]

Seems pretty snappy, wondering if there's a more efficient way of doing this.

Answer 1

Notes:

I completely overlooked the fact that rasher specified arbitrary precision input when crafting my functions. Because of this the numeric methods I used will not be as fast. However, to my surprise it seems that at least fn2 is still faster than the FoldList method on arbitrary precision data.

Timings with resets on average at about 1 in 40:

big = RandomInteger[{-1*^20, 1*^20}, 1*^6];
big = Clip[big, {-∞, 0.95*^20}, {0, 0}];

fn1[big, 0] // timeAvg
fn2[big]    // timeAvg

0.858

0.499

Not quite the performance on packed arrays demonstrated below, but still faster than FoldList in a number of cases.

---

If the resets are fairly sparse it is possible to beat the FoldList method by accumulating, then setting first zeros in the original list to appropriate negative values based on that pass, then accumulating again. As a proof of concept implemented only for resetting on zeros:

fn2[a_List] := Module[{x = a, acc = Accumulate@a, pos},
   pos = Split[#, # + 1 == #2 &][[All, 1]] & @
     SparseArray[Unitize@x, Automatic, 1]["AdjacencyLists"];
   x[[pos]] = -Differences @ Prepend[acc[[pos]], 0];
   Accumulate @ x
 ]

Edit: Adopting a method similar to my answer from Find continuous sequences inside a list this method is faster than the OP on rather more frequent splits as well:

fn3[a_List] :=
 Module[{x = a, acc = Accumulate@a, pos},
   pos = SparseArray[#]["AdjacencyLists"] &[
     Subtract[1, Unitize@x]*
      Prepend[Unitize@Differences@x, 1]
     ];
   x[[pos]] = -Differences @ Prepend[acc[[pos]], 0];
   Accumulate @ x
 ]

I named your function fn1. The timeAvg code has been posted many times.

On a list that resets on average one in ten elements:

big = RandomInteger[9, 1*^6];

Accumulate[big] // timeAvg
fn1[big, 0]     // timeAvg
fn2[big]        // timeAvg
fn3[big]        // timeAvg

0.004624

0.0656

0.0748

0.02808

Here fn3 is more than twice as fast as your original.
Now with resets on average one in one thousand elements:

big = RandomInteger[999, 1*^6];
(* other lines the same *)

0.004496

0.0718

0.01248

0.0156

Here both fn2 and fn3 are several times faster than the original, but now fn3 is slightly slower than fn2. With increasingly sparse resets fn2 continues to improve over fn3.

Answer 2

For brevity:

Map[Accumulate, Split[test, #2!=0&]] // Flatten

{0, 2, 4, 47839287, 47839289, 0, 0, 2, 0, 1, 3, 0}

... but not as fast as the OP :)

[ Thanks to MrWizard, changed SplitBy to Split which is more efficient ]