How to speed up pattern matching

Question

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.

2. 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[200], {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
]

Answer 1

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

Answer 2

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:

Internal`PartitionRagged[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.

Addendum:
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.