Sunday, 6 May 2012

Using Mathematica's Dispatch


How do I construct a Dispatch table?
Say you have a graph (network) consisting of n vertices in a loop:
In[1] := rules =
           With[{n = 1000},
             Table[ToString@i -> ToString@Mod[i + 1, n],
               {i, 0, n - 1}]];
You want to traverse the graph by applying these rewrite rules to an initial vertex. You can perform a single step with i /. rules but this is doing a linear search over rules trying to find the Rule with a lhs that matches the expression i. So applying the rules many times is slow:
In[2] := Nest[# /. rules &, 0, 10000] // AbsoluteTiming
Out[2] = {1.7880482, 0}
Mathematica's Dispatch allows us to precompute a hash table that turns the linear lookup into a constant-time lookup:
In[3] := dispatch = Dispatch[rules];
Applying the dispatch table many times obtains the same answer orders of magnitude faster:
In[4] := Nest[# /. dispatch &, 0, 10000] // AbsoluteTiming
Out[4] = {0.0550031, 0}
When is this advisable?
When:
  • You are doing many rewrites with the same set of rewrite rules, and
  • The set of rewrite rules contains at least 30 rules with constant lhs patterns, i.e. composed only from symbols, sequences and literals.
How does it work?
It just builds a hash table with the constant patterns as keys.
Are there alternative methods?
The most effective general approach is to rewrite the rules in another language. In particular, languages of the ML family (SML, OCaml and F#) have very efficient pattern match compilers and garbage collectors so they are able to rewrite terms much faster than Mathematica's general purpose rewriter does.

No comments:

Post a Comment