How to speed up pattern matching

Main Problem

Mr.Wizard posed this question when discussing another problem.

I reproduce the main part of Mr.Wizard's problem here:

MatchQ[{1, 2, 3, 4, 5}, {x__?((Echo[##]; False) &), y__}]

On evaluation we get the result:

1
1
1
1
False

The result is correct of course, and there should be four possible patterns, but it seems that, though MatchQ already knows the element 1 cannot pass the pattern test, it continues matching 1 three more times.

The extra matching is okay here as evaluation is fast enough, but this will consume a lot of time while matching long lists or dealing with patterns with long evaluation times, such as x__?((Echo[##]; Pause @ 1; False)&)

So the main problem is:

how to speed this process up and aviod repetitive calculation.

Some more explanation

I think some work-around is needed to get better results:

1. Unlike Condition(/;), PatternTest will check every element in a __?test-like pattern, not putting everything together. Thus this two pattern matching is different, and they give different results:

MatchQ[{1, 2, 3}, {__?((Echo@{##}; True) &)}];

MatchQ[{1, 2, 3}, {x__ /; (Echo@{x}; True)}];

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

Thus, in most cases, there'll be no problem of interference while using PatternTest; for example, testing 1 in Sequence[1, 2] will usually be the same as testing 1 in Sequence[1, 2, 3]. While in Condition, interference will be significant.

1. There are a few examples of interference. Take, for example, the answer of @Leonid Shifrin under the question I've mentioned at the beginning:

Module[{flag = False},
ClearAll[test3];
test3[x_] :=
With[{fl = flag}, If[! flag, flag = True];
Echo @ x;
fl]];
MatchQ[{-1, 2, 3, 4, 5}, {x__?test3, y__}];

-1
-1
2

But I think these cases usually won't occur, so I still want to know: are there any methods available to tell Mathematica, "I know testing result of elements will be the same in each trial, SKIP the repeated testing!"?

Some Notes

• I do NOT need a way to store the result of the pattern test, I'm trying to reduce the testing repetitions.

• The latter one will speed up the simple pattern matching process in long lists considerably; the first one won't, as the pattern test completes in a flash, but there're are simply too many flashes, thus the overall speed is low.

• Actually, the sample match I used as an example, the four tests complete in a flash, so memoizing will not speed things up. But if we can avoid the testing of the latter three 1, the whole process will be 4 times faster!

Additional and related examples

Here is an additional example that may help illustrate the inefficiency of reapplying the same test to the same element.

Replace[
{1.1, 2.2, 3, 4, 5},
{a___, x__?((Print[##]; IntegerQ[#]) &), y__} :>
{{a}, {x}, {y}}
]

1.1

1.1

1.1

1.1

2.2

2.2

2.2

3

{{1.1, 2.2}, {3}, {4, 5}}

This causes an algorithmic explosion in the time taken to process this pattern. In most applications it would be better if each element were only tested once. Observe that a test of a list of 200 elements performs almost twenty thousand tests:

i = 0;
MatchQ[N@Range, {a___, x__?((i++; IntegerQ[#]) &), y__}]
i
False

19900

This is not simply a matter handing the somewhat unusual case of a stateful test function (like the one with flag) as it is baked into expressly stateless patterns as well:

Needs["GeneralUtilities"]

BenchmarkPlot[
MatchQ[#, {a___, x__Integer, y__}] &,
RandomReal[99, #] &
, "IncludeFits" -> True
] • @Mr.Wizard Is my question clear enough to emphasize our points? – Wjx Aug 1 '16 at 13:19
• @Wjx I think the question is quite clear. Thank you for posting it. I added additional examples that I hope serve to illustrate the issue at a fundamental level without getting too far afield. – Mr.Wizard Aug 2 '16 at 1:01
• I'm just going to edit it to include a similar case: MatchQ[{1, 2, 3, 4, 5}, {___?((Echo[#, 1]; True) &), __?((Echo[{#, # > 2}, 2]; # > 2) &), __?((Echo[#, 3]; True) &)}] :) – Wjx Aug 2 '16 at 1:03
• After a more careful reading I realized your intent. Why not apply the test beforehand to all elements, cache the result and then pick your match according to the precomputed results? – LLlAMnYP Aug 2 '16 at 7:34
• Regarding the "some notes" section: I realize my suggestion doesn't reduce the number of tests in the simple example, but it could prevent the O(n^3) behavior in the edit. – LLlAMnYP Aug 2 '16 at 7:40

For MatchQ you can use Return[.., MatchQ]:

MatchQ[{1, 2, 3, 4, 5}, {x__?((Echo[##]; Return[False, MatchQ]) &), y__}] But I suspect one would like this to work with function argument checking, which it won't:

ClearAll[foo];
foo[{x__?((Print[Stack[]]; Return[False, MatchQ]) &), y__}] := "Hurrah!";

foo@Range@5 The output of Stack[] shows there's no function that can be substituted for MatchQ that would cause a return just from argument checking.

On the other hand, one could use MatchQ for checking the argument pattern:

ClearAll[foo];
foo[arg_] /; MatchQ[arg, {x__?((Echo[##]; Return[False, MatchQ]) &), y__}] := "Hurrah!"

foo@Range@5 • The logic of this use-case is simple enough to allow this simple optimization. One can imagine a more general question of how to find the optimal check on a given pattern. My feeling is that is impractical to solve. But one might be able to apply code-optimization techniques to the problem. – Michael E2 Aug 1 '16 at 14:15
• I'll have to say that this answer will do the job, but only for my far too simple illustrative code, instead of pattern matching in general. A simple alternation from MatchQ to Cases and return False only when inputing 1 will make this kind of solution fail. Its implementation is too narrow, actually not quite what I want. – Wjx Aug 1 '16 at 14:58
• @Wjx I don't understand your simple alternation. Cases[{{1}}, a_ /; MatchQ[a, {x__?((...; Return[False, MatchQ])&), z__}]]? Or perhaps you could clarify what you do want? (I can't fix something that's working on the example problem, obviously.) – Michael E2 Aug 1 '16 at 15:26
• Check @Mr.Wizard 's update~ – Wjx Aug 2 '16 at 1:22

This is an extended comment which may take some time to develop into an answer.

I'll focus on the O(n^3) algorithmic behavior observed on the benchmark plot and ways to combat that. I will not, however, handle the problem in the very first example (where four pattern tests were performed). I believe, one will need to essentially rewrite a pattern matcher, based on a more intelligent testing of conceivably valid combinations, in turn based on precomputed pattern tests.

Consider the example pattern {x__, y__?IntegerQ, z__}.

args = Range[1., 100.]~Join~{101, 102}~Join~Range[103., 200.];

Now I'll precompute the tests:

Boole@Through[{Map[True &], Map[IntegerQ], Map[True &]}[args]];

MapIndexed[# Last@#2 &, %, {2}];

pos = DeleteCases[%, 0, {2}];

And pos will have a list of lists, the first containing matching positions for x__, then for y__?IntegerQ, then for z__.

Next filter out obviously invalid positions (by invalid, I mean, that x__ must end before y__?IntegerQ ends and z__ must begin after y__?IntegerQ starts):

Do[pos[[i]] = Select[pos[[i]], # < Max[pos[[i + 1]]] &];
pos[[i + 1]] = Select[pos[[i + 1]], # > Min[pos[[i]]] &];, {i,
Length[pos] - 1}];
pos

(*
{{1,2,...,101},
{101,102},
{102,103,...,200}}
*)

Now is the tricky part which may be vulnerable to "algorithmic explosion". From this list of positions I wish to select permissible end-points of every pattern.

pos = pos~Join~{Length[args] + 1};
Do[pos[[i]] = Cases[pos[[i]], Alternatives @@ (pos[[i + 1]] - 1)], {i, Length[pos] - 1}];
pos = Most@pos
(* {{100, 101}, {101, 102}, {200}} *)
Tuples@%
(* {{100, 101, 200}, {100, 102, 200}, {101, 101, 200}, {101, 102, 200}} *)
Select[%, # === Union@# &]
(* {{100, 101, 200}, {100, 102, 200}, {101, 102, 200}} *)

Let's return the possible ways the original pattern can match our symbol args:

InternalPartitionRagged[args, Differences[{0}~Join~#]] & /@ %
(*{
{{..., 100.}, {101}, {102, 103., 104., ...}},
{{..., 100.}, {101, 102}, {103., 104., ...}},
{{..., 100., 101}, {102}, {103., 104., ...}}
}
*)

So by precomputing 200 tests it was possible to somewhat analytically reduce the number of combinations of arguments to 3, rather than 14752 calls to IntegerQ.

This guide should work for any amount of BlankSequence but there's a lot of bulletproofing to do here as well as early detection of outright non-matches. Hopefully, this can be a starting point for further efforts.

I checked the performances of my Cases statement with the following test:

BenchmarkPlot[
With[{r = {Range[3 #], Range[2 #, 4 #]}},
Cases[First@r, Alternatives @@ (Last@r)]] &,
# &,
"IncludeFits" -> True] O(n log(n)) is probably the bottleneck of this method and is quite a bit better than n^3.

• An intellegent try I shall say. but using this type of pattern matching style, you do can battle against the O(n^3) explosion, but if the whole list change to Range, you will still need to list out all possible matches first before selecting one of them, but the current pattern matcher can simply check once, taking almost no time, and give you a result, actually, much faster. Can you edit your post to include this feature? I mean, find the solution in some order, then quit evaluation as soon as you get a result. – Wjx Aug 4 '16 at 13:01
• My thought is to check possible matches still in a pattern matching way, but using some techniques to aviod repetitive checks and matches. But as you can see, seeking some way to manipulate the pattern matching process is quite hard...... – Wjx Aug 4 '16 at 13:04
• @Wjx You're right, it's much easier to find if a match is possible, than to return all possible matches. It'll take some work to optimize, for which I don't have time ATM. It'd be an interesting project to reimplement the pattern-matcher for this restricted problem that you posed. – LLlAMnYP Aug 4 '16 at 13:07
• Yes~ if this can be achieved, a lot of similar problems shall be solved too~ As you can see, mostly we're just using this form of simple patterns. :P – Wjx Aug 4 '16 at 13:13
• @Wjx scratch that, my posted function was wrong. Let me try and find a fix. – LLlAMnYP Aug 4 '16 at 13:41