Skip to main content
added 1 character in body
Source Link
Pillsy
  • 18.6k
  • 2
  • 48
  • 94

In addition to being kind of ugly and needing the For, it's also pretty slow, as functions that index into lists so often are. It takes about 0.04 seconds to process a list of 10000 random numbers (picked uniformly between 0 and 1). I futzed around with LengthWhile, TakeWhile and the like before deciding thathat I really needed the full generality of Fold to accomplish what I needed to do:

In addition to being kind of ugly and needing the For, it's also pretty slow, as functions that index into lists so often are. It takes about 0.04 seconds to process a list of 10000 random numbers (picked uniformly between 0 and 1). I futzed around with LengthWhile, TakeWhile and the like before deciding tha I really needed the full generality of Fold to accomplish what I needed to do:

In addition to being kind of ugly and needing the For, it's also pretty slow, as functions that index into lists so often are. It takes about 0.04 seconds to process a list of 10000 random numbers (picked uniformly between 0 and 1). I futzed around with LengthWhile, TakeWhile and the like before deciding that I really needed the full generality of Fold to accomplish what I needed to do:

Tweeted twitter.com/#!/StackMma/status/187829223824687104
Source Link
Pillsy
  • 18.6k
  • 2
  • 48
  • 94

Getting lengths of sublists that sum to more than one

I have a long list of numbers, and I'm interested in finding the length of each sublist that totals to more than 1, so for the list

{0.423768, 0.157558, 0.675251, 0.685209, 0.580772, 0.0230333, 
 0.927156, 0.506085, 0.0516773, 0.485349}

I would get the lengths {3, 2, 3}, as

Total[{0.423768, 0.157558, 0.675251}] == 1.25658
Total[{0.685209, 0.580772}] == 1.26598
Total[{0.0230333, 0.927156, 0.506085}] == 1.45627

The last two numbers total to 0.537026, so we ignore them. This has an easy imperative solution:

thresholdFor[nums_List] :=
  Module[{i = 0, sum = 0, k = 0},
   Reap[
     For[i = 1, i <= Length@nums, ++i,
      sum += nums[[i]];
      ++k;
      If[sum > 1,
       Sow[k];
       k = 0;
       sum = 0]]][[-1, 1]]];
thresholdFor[{}] = {};

In addition to being kind of ugly and needing the For, it's also pretty slow, as functions that index into lists so often are. It takes about 0.04 seconds to process a list of 10000 random numbers (picked uniformly between 0 and 1). I futzed around with LengthWhile, TakeWhile and the like before deciding tha I really needed the full generality of Fold to accomplish what I needed to do:

thresholdFold[nums_] :=
 Flatten@Last@Fold[
    With[{sum = #[[1]] + #2, length = #[[2]] + 1, acc = #[[3]]},
      If[sum > 1,
       {0, 0, {acc, length}},
       {sum, length, acc}]] &,
    {0, 0, {}},
    nums]

This is arguably more idiomatic, but it's even a bit slower than thresholdFor. I can speed thresholdFor up a lot by compilation (with a suitable adaptation to get rid of the Reap/Sow pair) and a little wrapper to handle the empty list properly:

compiledBody =
  Compile[{{nums, _Real, 1}},
   With[{n = Length@nums},
    Module[{result = ConstantArray[0, n], sum = 0.0, k = 0, fill = 0, i},
     For[i = 1, i <= n, ++i,
      sum += nums[[i]];
      ++k;
      If[sum > 1.0,
       result[[++fill]] = k;
       k = 0; sum = 0]];
     Take[result, fill]]]];

thresholdCompiled[nums_List] := compiledBody[nums];
thresholdCompiled[{}] = {};

This is dramatically faster after compilation--it runs in about 10 ms for the list of 100000 numbers, and is only about 10 times slower than Mean or Total on the same data. Still, I always think I'm going down a bit of a blind alley when I start using Compile to make imperative list-processing algorithms fast enough to use.

Finally, I did come up with something more Mathematica-esque, but it's actually much slower than the compiled solution (taking about 130 ms):

thresholdClip[nums_] :=
    Differences@Flatten@Position[
        FoldList[Clip[Plus[##], {0.0, 1.0}, {0.0, 0.0}] &, 0.0, randoms], 
        0.0]

I've tried a couple tweaks for speeding up thresholdClip, including one which replaces Position with Pick so I can compile the whole thing, but that didn't seem to do a lot of good.