# What is the fastest way to get a list of subexpressions and their positions?

I have spent quite some time trying to figure out what the fastest way is to get a list lists of all subexpressions and their positions. I have tried things with MapIndexed, which seems ideal in cases where we have an expression in which no functions with Hold-Attributes are present that we can let evaluate freely. For Held expressions, however, I found using MapIndexed complicated and I was unable to get a practical solution using this. Furthermore, I have tried things with Extract and Position.

All these things were hinted at in the comments of/answers to the positionFunction question by Mr.Wizard, which caused me to be interested in this. Because I have spent time on this and because I feel this is quite a fundamental question, I would like to get some feedback. To be fair, I am also quite glad with my own answer, as it is considerably faster than the alternatives I found (although it took me a long time), but if there are better alternatives I would be even gladder to know. Lastly, it may be nice for me to refer to this Q&A later, if I ever write a good answer to Mr.Wizards question.

The question is: What is the fastest way to get a list of lists of subexpressions and their positions, that works with held expressions?

Test expressions

Let's make a big expression to do tests with. Let

body[i_][n_] := If[n < i, head[body[i][n + 1], body[i][n + 1]], 1];


We have

LeafCount[tree12] == 2^12 && LeafCount[tree3] == 2^3


(True)

-

I'm not certain I understand your goals, though I too wish there were a cleaner way to do this.
I presume that you are dissatisfied with the performance of this fairly direct solution:

index[expr_] := {Extract[expr, #, HoldComplete], #} & /@ Position[expr, _]


Your own method using both Position and Level is a clever way to vectorize this as it were. I do not understand why you gave your toExprPosLists function a hold attribute at this would seem to only complicate using it. Perhaps you would find value in this:

index2[expr_, lev_ : {0, -1}] :=
HoldComplete @@ Position[expr, _, lev]}, HoldComplete]


This returns something similar to your function and it is faster:

time = Function[x, First@Timing@Do[x, {500}]/500, HoldAll];

toExprPosLists @@ {tree12} // time
index[tree12]              // time
index2[tree12]             // time

0.003432

0.005648

0.00184

-
Ah yes, it is faster indeed :). And even applying Rule on level {1,1} afterwards is faster than the alternative with Inner[Rule, exprs, pos, HoldComplete]. I do not see why though. You are right about the argument HoldAllComplete. If the user has not given his expression head HoldComplete, then it will be really hard to stop the expression from rebuilding anyway (though it is possible, using OwnValues). One subtlety is that it may be nicer to end up with something like HoldComplete[{...}] rather than HoldComplete[...]. Anyway, it is not so important. +1, exactly what I was looking for. – Jacob Akkerboom Jun 6 '13 at 8:43
@Jacob Glad I could help, even if I was bumbling. :-) If you want the inner list try: List @@@ HoldComplete @@ {HoldComplete[1 + 1, 2 + 2]} (faster) or HoldComplete[1 + 1, 2 + 2] /. h_[a__] :> h[{a}]. I suppose index2 is faster because it is just less convoluted. – Mr.Wizard Jun 6 '13 at 8:49
You provoked an edit with that comment ;). Note that I am not offended by the word convoluted. However, I think I do have some valid points and I hope they are not discarded because your code is so much better (and my code is so long). I'm pretty sure I have showed that Inner is just inferior to Thread if Thread can be used. That is unexpected to me, but it is exactly the kind of thing I'd like to be aware of :). – Jacob Akkerboom Jun 6 '13 at 13:23

Solutions with Inner

Here is the function I came up with

ClearAll[toExprPosLists];
SetAttributes[toExprPosLists, HoldAllComplete]
toExprPosLists[expr_] :=
Inner @@
Function[
Hold@
Evaluate[
List,
Unevaluated @@
Level[Unevaluated@expr, {0, Infinity}, #, Heads -> True],
Position[Unevaluated@expr, _],
#
]
]@Function[Null, HoldComplete[List@##], HoldAllComplete]


We then have

head = 6;
{
# (*timing*),
{
(HoldComplete @@@ #2)[[1, All]] // Length,
Position[tree12HC, _] // Length,
2^12 + 2^11 + 2
} (*number of subexpressions*)
,
#2[[All, ;; 5]] (*sample of subexpressions*)
} & @@
(toExprPosLists @@ List@tree12HC // Timing)


{
0.015144, (timing)
{6146, 6146, 6146}, (number of subexpressions)

HoldComplete[{{HoldComplete, {0}}, {head, {1, 0}}, {head, {1, 1, 0}}, {head, {1, 1, 1, 0}}, {head, {1, 1, 1, 1, 0}}}] (sample of subexpressions)
}

Remarks

All the HoldComplete wrappers and the HoldAllComplete attributes serve to minimize overhead. To see what I mean, consider the difference between

head = List;
Trace[Hold @@ tree12HC, TraceOriginal -> True] // LeafCount


16411

head = List;
Trace[tree12HC, TraceOriginal -> True] // LeafCount


4101

I am not sure if I have succeeded in stopping all "rebuilding of expressions". But at least I have kept such considerations in mind while making the function :).

"Less convoluted"

Note that we could also have written

ClearAll[toExprPosLists3];
toExprPosLists3[expr_] :=
Inner[
List,
Level[Unevaluated@expr, {0, Infinity}, HoldComplete, Heads -> True],
HoldComplete@@Position[Unevaluated@expr, _],
HoldComplete
]


But this appears to be slower. Also this does not look much more convoluted than Mr.Wizards answer, it only uses Inner instead of Thread. However, it is slower than the function I defined above. I think I understand a little bit why this function is slower, that is why I came up with the "convoluted version" in the first place :). Below is an explanation.

All of this has to do with the fact that it takes a bit of time to do something like HoldComplete@@expressionWithManyArguments. That is also the reason why I let the function return something of the form HoldComplete[List[___]] rather than HoldComplete[___], because it is more likely that you will need a list than something with head HoldComplete. This allows you to prevent one more List@@expressionWithManyArguments. Also in case you do var = expressionWithManyArguments and then do List@@var, you are using twice as much memory as necessary.

However, all of that optimization/"convolution" is minor compared to the difference in performance between Inner and Thread, it seems.

To take this argument that Inner is worse than Thread to the extreme, let's make our own version of Inner (that will only work correctly with a very specific subset of possible arguments). We could set

myInner[head1_, exprs__, head2_] :=


and

ClearAll[toExprPosLists4];
SetAttributes[toExprPosLists4, HoldAllComplete]
toExprPosLists4[expr_] :=
myInner[
List,
Level[Unevaluated@expr, {0, Infinity}, HoldComplete,
HoldComplete @@ Position[Unevaluated@expr, _],
HoldComplete
]


Which turns out to be faster, because as it turns out Inner is just not suitable for the job.

Comparison of timings

toExprPosLists @@ tree12HC // Timing // First
toExprPosLists3[tree12] // Timing // First
toExprPosLists4 @@ tree12HC // Timing // First
index2[tree12, {0, Infinity}] // Timing // First


0.015313
0.016765
0.010508
0.006448

So, Thread seems to be the best option for this (I think it is not possible to use MapThread, though maybe we can use InheritedBlock). I think there is no optimization to be done w.r.t avoiding apply, because of the stringent syntax of Thread. In my opinion, it is a bit of a shame we end up with something matching HoldComplete[___] rather than HoldComplete[{___}], but I do not see a good way around this.
Here's an observation of my own: you appear to be confusing HoldAllComplete with HoldComplete; the former is an attribute, not a container. – Mr.Wizard Jun 7 '13 at 11:48