0
$\begingroup$

Given a list L. It is mathematically proven that there is no element in L matching 2 or more patterns in patt1/patt2/patt3/patt4/.../patt10. (Note that one can express a criteria/test into a pattern. I think it is safe to think as 'criteria' instead of 'pattern', if you want.)

Now I want get
positions matching patt1,
positions matching patt2,
positions matching patt3,
positions matching patt4,
...
positions matching patt10.

One method is

{Position[L,patt1],Position[L,patt2],Position[L,patt3],...,Position[L,patt10]}

But, it looks for each element 10 times.

Maybe we can increase the performance by

  1. get positions matching patt1
  2. except positions matching patt1, get positions matching patt2.
  3. except positions matching patt1,2, get positions matching patt3.
  4. except positions matching patt1,2,3, get positions matching patt4. ...
  5. except positions matching patt1,2,3,...,10 get positions matching patt10.

Or we may increase the performance by..

'take the first element of L, check whether it matches patt1,patt2,patt3,patt4,...,patt10 in order. If it matched patt3, for example, then record 'the first element of L matched patt3' and then go to the next element. Check whether it matches patt1,patt2,patt3,patt4,...,patt10 in order. This time, for example, it doesn't match any pattern. Then go to the next element. It goes on like this.

The question is related to the built-in command GatherBy, but for GatherBy, we cannot restrict the range of values. (always all values.) And the output of GatherBy does not show values.

First I am not sure which method is the best (Because thinking and reality are always different.) Considering the performance, are there any commonly used techniques for these problem?

I made a problem in a hurry to give an example :

A = RandomInteger[{1, 100}, 1000];
B = RandomInteger[100, #] & /@ A;

The problem is :
Select level-1 positions in B, whose length is 2
Select level-1 positions in B, whose length is 3
Select level-1 positions in B, whose length is 5
Select level-1 positions in B, whose length is 7
...
Select level-1 positions in B, whose length is 97

There may be much better example though.

$\endgroup$
5
  • $\begingroup$ An example would be useful $\endgroup$
    – Carl Woll
    May 9, 2022 at 20:40
  • 2
    $\begingroup$ You could try to do something like Replace[L, {patt1 -> 1, patt2->2, ...}, {1}] $\endgroup$
    – Carl Woll
    May 9, 2022 at 20:46
  • 1
    $\begingroup$ If I'm understanding your question, you know a few different ways to get the results you want, but you are looking for the most performant. Without knowing the size and shape of your data, it will be very difficult to know how to optimize. I think you need to provide more info about the types of patterns, the shape of L, and the size of the problem. $\endgroup$
    – lericr
    May 9, 2022 at 20:49
  • $\begingroup$ @Carl woll, that kind of thing is what I wanted! Thinking again, it is at least theoretically the best. $\endgroup$
    – imida k
    May 9, 2022 at 20:57
  • $\begingroup$ @lericr, thank you, I want to write more later when I have time. $\endgroup$
    – imida k
    May 9, 2022 at 21:00

1 Answer 1

1
$\begingroup$

Granted that your example may not be actually representative of what you ultimately want, here's an attempt:

(* beefed up your list a bit *)
B = Table[ConstantArray[1, RandomInteger[1000]], 1000000]

PositionIndex seems like it will be interesting to you. We can first map the property you want to check. We'll start with a simplification: just Length.

AbsoluteTiming[PositionIndex[Length /@ B]] // Short
(* {0.232473,<|908->{1,657,1211,1595,<<967>>,996367,997446,998904,999600},<<999>>,35->{<<1>>}|>} *)

We can select just the ones with the desirable attribute with KeySelect:

AbsoluteTiming[KeySelect[PositionIndex[Length /@ B], PrimeQ]] // Short
(* {0.228517,<|463->{5,2118,3597,3981,<<961>>,995791,996307,997621,997842},<<166>>,193->{<<1>>}|>} *)

Alternatively, we can first map the property we want and then use PositionIndex:

PrimeLengthOrOtherwise[arg_] :=
  Which[
    PrimeQ[Length@arg], Length@arg,
    True, -1];
AbsoluteTiming[PositionIndex[PrimeLengthOrOtherwise /@ B]] // Short
(* {1.00528,<|-1->{1,2,3,4,6,<<832394>>,999994,999995,999996,999998,999999},<<167>>,19-><<1>>|>} *)

You could use something other than -1 if it would be clearer. It's pretty easy to now ignore that one "otherwise" value, so I think this is still in the spirit of your question and addresses your objection to GatherBy.

I don't know if I scaled the problem sufficiently, but hopefully the timings will give you some idea of what sort of performance you can expect if your real scenario is close to this toy example.

$\endgroup$
2
  • $\begingroup$ Thank you, I'll test the performance if I have time! $\endgroup$
    – imida k
    May 10, 2022 at 15:07
  • $\begingroup$ The method (of @lericr) is unbelievably fast. PositionIndex[PrimeLengthOrOtherwise /@ B];took 1.20 seconds while Select[Range[1000000], PrimeQ[Length[B[[#]]]] &]; took 1.07 seconds. The latter only offers index of element with prime number length lumped together, but just a little faster. $\endgroup$
    – imida k
    May 16, 2022 at 13:09

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.