## 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}
``````