# Gathering a List efficiently

In my situation, I have a large list of objects L={A,B,C,D,E,...} and a function Q[] applying to them, which will produce the values only from the set {0,2,4,6,8}.

(e.g. Q[] can be Length[] and my objects ABCDE are lists of certain sizes)

I want to split the list so that I will obtain 5 lists L0,L2,L4,L6,L8, each list contains only the index of the corresponding elements in L (Because I want to keep track of the location of those objects in the original list). Is there an effective way to do this, other than doing a for loop if statement and calling AppendTo[] adding the index each time?

(The Mathematica function GatherBy[] will only give the element of the list itself, but not the index in the original list which I want.)

For example, for the input list

L={{1,2},{3,4,5,6},{7,8,9,10},{11,12}}


and

Q=Length


I want

{L0,L2,L4,L6,L8} = {{},{1,4},{2,3},{},{}}


since sublists of length 2 are at positions 1 and 4, length 4 -- at 2 and 3, and there are no sublists of length 0, 6, 8.

• Since you'll probably end up with an association, you could use Lookup with the optional argument to handle missing cases (L4 be an empty list). – LLlAMnYP Jul 27 '18 at 8:08
• GatherBy[Range[Length@L], Q[L[[#]]]&]? – kglr Jul 27 '18 at 8:26
• >>minimal example: L={{1,2},{3,4,5,6},{7,8,9,10},{11,12}}, Q=Length[], Then {L0,L2,L4,L6,L8} = {{},{1,4},{2,3},{},{}} – Ivan Jul 27 '18 at 8:52
• Thanks for the edit but the input needs to contain information about values you care about. E.g. only 2 and 4 long lists exist but you want to lookup 0,2,4,6,8. – Kuba Jul 27 '18 at 9:43
• @Kuba my bad, I should have left a comment when I edited this. Perhaps you or OP have ideas how to make things clearer? – LLlAMnYP Jul 27 '18 at 10:33

SeedRandom
L = Table[RandomChoice[{1, 4} -> {{}, RandomChoice[CharacterRange["A", "G"],
RandomChoice[{2, 4, 6, 8}]]}], {15}]


{{"G", "E", "F", "C"}, {"G", "D", "B", "C", "D", "A"}, {"D", "B", "E", "E", "F", "D", "G", "G"}, {}, {"C", "C", "F", "A", "D", "C"}, {"B", "A", "G", "B"}, {"A", "E"}, {}, {}, {"C", "F"}, {"F", "E", "C", "E"}, {"G", "E"}, {"C", "E", "C", "A", "B", "A"}, {"G", "F", "G", "F", "D", "B", "A", "B"}, {"A", "C", "B", "E"}}

Q = Length;
{L0, L2, L4, L6, L8} = Pick[Range @ Length @ L, #- Q /@ L, 0] & /@ {0, 2, 4, 6, 8}


{{4, 8, 9}, {7, 10, 12}, {1, 6, 11, 15}, {2, 5, 13}, {3, 14}}

Or, as suggested by Kuba in comments:

{L0, L2, L4, L6, L8} = PositionIndex[Q /@ L] /@ {0, 2, 4, 6, 8} /. _Missing-> {}


same output

• Thanks for the idea! and the "Missing" part also helps~ – Ivan Jul 27 '18 at 15:17

Pulling my approach out from the comments:

lists = {{1, 2}, {3, 4, 5, 6}, {7, 8, 9, 10}, {11, 12}};
func = Length;
values = {0, 2, 4, 6, 8};
Lookup[PositionIndex[func /@ lists], values, {}]

{{}, {1, 4}, {2, 3}, {}, {}}


I thought kglr's approach would be pretty fast (as Pick often is), but since we're dealing with unpacked arrays, it took a lot of special effort to get the most out of it. Here's a performance comparison.

SeedRandom
lists = Table[
RandomChoice[{1, 4} -> {{},
RandomChoice[CharacterRange["A", "G"],
RandomChoice[{2, 4, 6, 8}]]}], {100000}];
values = {0, 2, 4, 6, 8} // DeveloperToPackedArray;
(r1 = Pick[ConstantArray[Range@Length@lists, Length@values],
ConstantArray[
func /@ lists // DeveloperToPackedArray,
Length@values
] - values, 0
]); // AbsoluteTiming (* my attempt to vectorize kglr's solution *)

(* kglr's solution as is *)
(r2 = Pick[Range@Length@lists, # - func /@ lists, 0] & /@ values); // AbsoluteTiming

(* my approach *)
(r3 = Lookup[PositionIndex[func /@ lists // DeveloperToPackedArray], values, {}]); // AbsoluteTiming

r1 === r2 === r3

{0.0450857, Null}
{0.122854, Null}
{0.0340838, Null}
True


I suggest that instead of {L0, L2, L4, L6, L8} you use {lq, lq, lq, lq, lq}.

My approcach

lq = GroupBy[
MapIndexed[{##} &, L]
, Q@*First -> Last@*Last
]


But I have to admit that @Kuba's is the best solution to my taste

lq = PositionIndex[Q /@ L]
`