4
$\begingroup$

I have a list of numbers and I am looking for a way to most efficiently find positions of values that satisfy a certain condition and group those positions that are sequential. To illustrate, a simple list can look like

x={1,2,4,6,2,3,4,5,7,9,1,3,4,1}

and I am interested in all numbers that are greater than 2 and so I expect the return to look like:

res={{3,4},{6,7,8,9,10},{12,13}}

Alternatively, I would also need the result being the values in x however grouped in the same manner.

The stress is also on effectivness, this will be applied on a number of 100 MB data files. My initial idea was: Position[x, n_ /; n > 50] // Flatten and then somehow go through the output and determined if the next position is previous plus 1 but I think this is not very effective (also I have no idea how to do it without complex loops).

$\endgroup$
  • 1
    $\begingroup$ You can use Split to do the last step, or fancier stuff from this question. $\endgroup$ – wxffles Mar 23 '16 at 21:15
  • 1
    $\begingroup$ @leosenko, your version would look like Split[Flatten@Position[list, n_ /; n > 2], #2 - #1 == 1 &] $\endgroup$ – garej Mar 24 '16 at 5:59
2
$\begingroup$

You can use the BoolEval function from the BoolEval package. You can load it as follows, for example:

Import["https://bitbucket.org/szhorvat/booleval/raw/8e1eaf980500b5ff066b2b4bf3a61c1ad2e9c02d/BoolEval.m"]

Here is a function based on that:

ClearAll[getSplitPositions];
SetAttributes[getSplitPositions, HoldRest];
getSplitPositions[list_, crit_] :=
  With[{pos = Sort@Pick[Range[Length[list]], BoolEval[ crit], 1]},
    If[pos === {}, Return[{}]];
    Internal`PartitionRagged[
      pos,
      Composition[
        Append[#, Length[pos] - Total[#]] &,
        Differences,
        Prepend[0],
        Flatten,
        #["NonzeroPositions"] &,
        SparseArray,
        Unitize,
        Differences@# - 1 &
      ] @ pos
    ]
  ];

It does reproduce you desired output:

list = {1, 2, 4, 6, 2, 3, 4, 5, 7, 9, 1, 3, 4, 1};
getSplitPositions[list, list > 2]

(* {{3, 4}, {6, 7, 8, 9, 10}, {12, 13}} *)

And it can handle a list of million numbers in a fraction of a second:

lrgTest = RandomInteger[{1, 1000}, 1000000];
getSplitPositions[lrgTest, 250 < lrgTest < 300] // Length // AbsoluteTiming

(* {0.178297, 46292} *)

It does, however, have an issue - it unpacks, presumably due to certain subtleties of the BoolEval implementation. Here is a version of BoolEval that won't unpack:

ClearAll[BoolEval];
SetAttributes[BoolEval, HoldAll];
BoolEval[condition_] := 
  Replace[
    Unevaluated[condition], 
    BoolEval`Private`rules, 
    {0, Infinity}, 
    Heads -> True
  ]

In this particular case, the speed is the same, but the memory use should probably be better with this version.

$\endgroup$
  • 1
    $\begingroup$ For people reading this: BoolEval is now fixed and will not unpack. There is a compromise that had to be made: all relational and logical operators that appear literally in the argument of BoolEval are overloaded. BoolEval is meant to be used only with relatively simple and expressions that are literally spelt out. $\endgroup$ – Szabolcs Feb 22 '17 at 9:57
  • $\begingroup$ @Szabolcs Great! Thanks for the info. $\endgroup$ – Leonid Shifrin Feb 22 '17 at 13:44
0
$\begingroup$
Clear[g]
g[list_, limit_] := Module[{l, l2},
  l = (list - limit);
  l2 = Unitize[l] UnitStep[l] Range[Length[list]];
  Split[l2, #1 != 0 && #2 != 0 &] /. {0} -> Sequence[]];

g[x, 2]
(*{{3, 4}, {6, 7, 8, 9, 10}, {12, 13}}*)

Testing it with Leonid Shifrin (with only one limit):

g[lrgTest, 250] // Length // AbsoluteTiming
(*{1.25263, 187504}*)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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