How can I ensure that I am constructing patterns in the most efficient way possible?

Question

Inspired by this answer, I am interested to know if there are best practices or rules of thumb for constructing patterns, for example for use in function definitions (f[x_Pattern ] or f[x:Pattern]), replacement rules (expr /. x:Pattern :> y), or functions that use patterns as arguments (e.g. Cases).

Leonid mentions that "syntactic patterns", without Condition or PatternTest elements, are faster for things like Cases. Is this a general observation for all pattern-matching constructs in Mathematica, or is it specific to Cases? Is there a definition of a syntactic pattern as opposed to other kinds?

And if the test in question requires "slower" constructs like BlankNullSequence (___), are there workarounds or optimisations that are effective, or is it not worth the time spent optimising code?

Answer 1

Some pitfalls in pattern-construction

You should ask several questions:

• Will your pattern involve frequent invocation of the evaluator (this happens if it contains Condition and / or PatternTest, and is tested many times). If yes, this will slow down the pattern-matcher.

Here is an example taken from this answer

randomString[]:=FromCharacterCode@RandomInteger[{97,122},5];
rstest = Table[randomString[],{1000000}];

In[102]:= MatchQ[rstest,{__String}]//Timing
Out[102]= {0.047,True}

In[103]:= MatchQ[rstest,{__?StringQ}]//Timing
Out[103]= {0.234,True} 

• Will your pattern make the pattern-matcher perform many a-priori doomed matching attempts (and thus, underutilize the runs of the pattern-matcher)? If yes, this will slow it down a lot. Patterns with BlankSequence or BlankNullSequence are notorious for that, particularly in combination with ReplaceRepeated.

For example, this list sorting is very inefficient:

list//.{left___,x_,y_,right___}/;x>y:>{left,y,x,right}

However, there are cases where such patterns are very efficient as well, such as in this answer.

• Will your pattern lead to excessive copying of parts? This happens also for patterns like x___, because the rule like {x_,y___}:>{y} will copy the entire sequence (array) y during the match. This is because lists are implemented as arrays in Mathematica.

As in example here, consider the following implementation of mergeSort, taken from my answer in this thread:

Clear[merge]; 
merge[x_List, y_List] := 
 Block[{merge}, 
   Flatten[merge[x, y] //. {
    merge[{a_, b___}, {c_, d___}] :> 
      If[a < c, 
         {a, merge[{b}, {c, d}]}, {c, merge[{a, b}, {d}]}
      ], 
      merge[{}, {a__}] :> {a}, 
      merge[{a__}, {}] :> {a}}]]  

This one is very slow. The detailed analysis is in the same answer I linked to, but here is the version based exclusively on ReplaceRepeated, but made efficient because it uses linked lists:

Clear[toLinkedList]; 
toLinkedList[x_List] := Fold[{#2, #1} &, {}, Reverse[x]]; 
Module[{h, lrev}, 
  mergeLinked[x_h, y_h] := 
    Last[{x, y, h[]} //. {
        {fst : h[hA_, tA_h], sec : h[hB_, tB_h], e_h} :> 
              If[hA > hB, {tA, sec, h[hA, e]}, {fst, tB, h[hB, e]}], 
        {fst : h[hA_, tA_h], h[], e_h} :> {tA, h[], h[hA, e]}, 
        {h[], sec : h[hB_, tB_h], e_h} :> {h[], tB, h[hB, e]}}]; 

  lrev[set_] := Last[h[set, h[]] //. h[h[hd_, tl_h], acc_h] :> h[tl, h[hd, acc]]]; 

  sort[lst_List] := 
     Flatten[Map[h[#, h[]] &, lst] //. 
         x_List :>       
           Flatten[{toLinkedList@x, {}} //.
            {{hd1_, {hd2_, tail_List}}, accum_List} :> 
               {tail, {accum, lrev@mergeLinked[hd1, hd2]}}], 
         Infinity, h]]; 

Just only due to the use of linked lists and resulting from them memory/run-time savings, this implementation recovers the correct n log n asymptotic complexity of the merge sort angorithm, even though ReplaceRepeated is used all over. The benchmarks can be found in the quoted post.

• Does your pattern lead to accidental unpacking of packed arrays, even when that is not necessary? This can slow things down significantly. In this answer, I discussed some possible work-arounds to avoid such situtations.

Summary and recommendations:

---

• Be careful with __ and ___
• Be careful with ReplaceRepeated
• Try to construct patterns such as to minimize failed pattern-matching attempts.
• Avoid Condition and PatternTest whenever possible, and use syntactic patterns
• Watch out for unpacking during the pattern-matcher
• In place of __ and ___, try using linked lists when you can

Answer 2

In the case of patterns, you should try to use the most specific pattern possible.

The BlankNullSequence aggressively tries to match and will recursively trace through your expressions to find something that fits. This takes a lot of time, so you should only use it when necessary.

When you use the most specific pattern possible, you save Mathematica from having to do more work than it needs to. Sometimes you have to use BlankNullSequence, but if you can avoid it then by all means do so.