General
When you define a type based on a head, like
f[x_List, y_List]:=...
the test happens entirely in the pattern-matcher, not involving the main evaluator. I call such patterns "syntactic". Pattern tests on such patterns are usually faster or much faster. The reason is that all the matching happens entirely in the pattern-matcher, and the latter only needs to operate on the syntactic form of expression (FullForm), to establish the fact of the match. This can also be viewed as a strongest typing scheme available in Mathematica.
When you defined the patterns with ? (PatternTest) or /; (Condition), you invite the main evaluator to join the game. So when you define a function like
f[x_?ListQ, y_?NumericQ]:=...,
the pattern-matcher always calls the main evaluator in order to pattern-match these patterns. Because of this, such tests are more general, but also can be significantly slower. They can also induce side effects, through the predicate's code executed by the main evaluator - which can't happen with the _h - style patterns.
Performance
Here is a comparison with a built-in atomic type (strings):
chars = RandomChoice[CharacterRange["a", "z"], 100000];
MatchQ[chars, {___?StringQ}] // AbsoluteTiming
MatchQ[chars, {___String}] // AbsoluteTiming
(* {0.018108, True} *)
(* {0.001687, True} *)
We can see an order of magnitude speed difference. This becomes even worse when the testing function is a little more complex:
ClearAll[f];
symtest = f /@ Range[100000];
MatchQ[symtest, {___f}] // AbsoluteTiming
MatchQ[symtest, {___?(Function[Head[#] === f])}] // AbsoluteTiming
(* {0.002725, True} *)
(* {0.087275, True} *)
The difference is most dramatic for packed arrays, where, in addition to the usual difference explained above, many pattern-testing system functions have been specially overloaded on certain patterns, so that they perform a constant-time check:
tst = Range[10000000];
MatchQ[tst, {___Integer}] // AbsoluteTiming
MatchQ[tst, {___?IntegerQ}] // AbsoluteTiming
(* {5.*10^-6, True} *)
(* {2.4889, True} *)
Evaluation
The differences outlined above have implications for evaluation control. In particular, for functions which hold their argument, the "syntactic" patterns won't always work. For example:
ClearAll[a, f, g];
a = Range[10];
SetAttributes[{f,g}, HoldFirst];
f[l_List]:=l;
g[l_?ListQ]:=l;
{f[a], g[a]}
(* {f[a], {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}} *)
The point is, that even though a stores a List, f can't check that by only using the pattern-matcher. In contrast to this, g calls the main evaluator, which confirms that a evaluates to a List.
This effect has also another side: when you use a pattern like a_List in a Hold* - function, you can be sure that there will be no evaluation leaks, while in cases where you use the tests based on Condition or PatternTest, you have to make an extra effort to ensure that (if that is desired). For example:
ClearAll[a];
a := Print["Leak!"]
Cases[Unevaluated[{a, {a, {a}}}], s_List :> Hold[s], Infinity, Heads -> True]
(* {Hold[{a}], Hold[{a, {a}}]} *)
while
Cases[Unevaluated[{a, {a, {a}}}], s_?ListQ :> Hold[s], Infinity, Heads -> True]
During evaluation of In[296]:= Leak!
During evaluation of In[296]:= Leak!
During evaluation of In[296]:= Leak!
During evaluation of In[296]:= Leak!
During evaluation of In[296]:= Leak!
During evaluation of In[296]:= Leak!
(* Out[299]= {Hold[{a}], Hold[{a, {a}}]} *)
In this particular case, one would have to write someting like this, to avoid the leaks:
Cases[
Unevaluated[{a, {a, {a}}}],
s_?(Function[Null, ListQ[Unevaluated[#]], HoldAll]) :> Hold[s],
Infinity,
Heads -> True
]
(* {Hold[{a}], Hold[{a, {a}}]} *)
Pre-filtering
It is often useful to use the _h patterns even if they are not enough be themselves, for pre-filtering purposes.
Here is an example - first, a simple custom test for a list:
ClearAll[smallListQ];
smallListQ[x_ /; ListQ[x] && Length[x] < 20 && Total[x^2] < 1000] := True;
smallListQ[_] := False
Now, the same test, but with the part of a pattern using _h idiom:
ClearAll[smallListQBetter];
smallListQBetter[x_List /; Length[x] < 20 && Total[x^2] < 1000] := True;
smallListQBetter[_] := False
Compare performance:
smallListQ /@ Range[100000]; // AbsoluteTiming
(* {0.153377, Null} *)
smallListQBetter /@ Range[100000]; // AbsoluteTiming
(* {0.058185, Null} *)
In some cases, the difference may be far greater
When to use which
- Whenever you can get away with purely "syntactic" tests, surely du use them.
- Also, they can often be used when you defined a custom data type based on some head, used as a container for data. In those cases, the
_h test serves as a test for a given data type.
- Often you can't avoid using the
_?predicate or x_/;predicate[x] types of patterns, because the tests must call the main evaluator, for whatever reason. Just be aware of performance and evaluation control - related implications of this method
- Often one can combine both styles, using the
_h - style patterns as a pre-filtering device. This can improve both the robustness of the code (stronger typing), and the performance.
Related discussions
