functions - Partitioning a list when the cumulative sum exceeds 1

I have a long list of say 1 million Uniform(0,1) random numbers, such as:

 dat = {0.71, 0.685, 0.16, 0.82, 0.73, 0.44, 0.89, 0.02, 0.47, 0.65}

I want to partition this list whenever the cumulative sum exceeds 1. For the above data, the desired output would be:

{{0.71, 0.685}, {0.16, 0.82, 0.73}, {0.44, 0.89}, {0.02, 0.47, 0.65}}

I was trying to find a neat way to do this efficiently with Split combined with say Accumulate or FoldList or Total, but my attempts with Split have not been fruitful. Any suggestions?

Answer

dat = {0.71, 0.685, 0.16, 0.82, 0.73, 0.44, 0.89, 0.02, 0.47, 0.65};

Module[{t = 0},
  Split[dat, (t += #) <= 1 || (t = 0) &]
]

{{0.71, 0.685}, {0.16, 0.82, 0.73}, {0.44, 0.89}, {0.02, 0.47, 0.65}}

Credit to Simon Woods for getting me to think about using Or in applications like this.

---

Performance

I decided to make an attempt at a higher performing solution at the cost of elegance and clarity.

f2[dat_List] := Module[{bin, lns},
   bin = 1 - Unitize @ FoldList[If[# <= 1`, #, 0`] & @ +## &, dat]; 
   lns = SparseArray[bin]["AdjacencyLists"] ~Prepend~ 0 // Differences;
   Internal`PartitionRagged[dat,
      If[# > 0, Append[lns, #], lns] &[Length @ dat - Tr @ lns]
   ]
 ]

And a second try at performance using Szabolcs's inversion:

f3[dat_List] :=
  Module[{bin},
    bin = 1 - Unitize @ FoldList[If[# <= 1`, #, 0`] & @ +## &, dat];
    bin = Reverse @ Accumulate @ Reverse @ bin;
    dat[[#]] & /@ GatherBy[Range @ Length @ dat, bin[[#]] &]
  ]

Using SplitBy seems natural here but it tested slower than GatherBy.

Modified October 2018 to use Carl Woll's GatherByList:

GatherByList[list_, representatives_] := Module[{func},
    func /: Map[func, _] := representatives;
    GatherBy[list, func]
]

f4[dat_List] :=
  Module[{bin},
    bin = 1 - Unitize @ FoldList[If[# <= 1`, #, 0`] & @ +## &, dat];
    bin = Reverse @ Accumulate @ Reverse @ bin;

    GatherByList[dat, bin]
  ]

The other functions to compare:

f1[dat_List] := Module[{t = 0}, Split[dat, (t += #) <= 1 || (t = 0) &]]

fqwerty[dat_List] :=
  Module[{f},
    f[x_, y_] := Module[{new}, If[Total[new = Append[x, y]] >= 1, Sow[new]; {}, new]];
    Reap[Fold[f, {}, dat]][[2, 1]]

  ]

fAlgohi[dat_List] :=
 Module[{i = 0, r},
  Split[dat, (If[r, , i = 0]; i += #; r = i <= 1) &]
 ]

And a single point benchmark using "a long list of say 1 million Uniform(0,1) random numbers:"

SeedRandom[0]
test = RandomReal[1, 1*^6];


fqwerty[test] // Length // RepeatedTiming
fAlgohi[test] // Length // RepeatedTiming
f1[test]      // Length // RepeatedTiming
f2[test]      // Length // RepeatedTiming
f3[test]      // Length // RepeatedTiming
f4[test]      // Length // RepeatedTiming
main1[test]   // Length // RepeatedTiming    (* from LLlAMnYP's answer *)

{6.54, 368130}

{1.59, 368131}

{1.29, 368131}

{0.474, 368131}

{0.8499, 368131}


{0.4921, 368131}

{0.2622, 368131}

I note that qwerty's solution has one less sublist in the output because he does not include the final trailing elements if they do not exceed one. I do not know which behavior is desired.