Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Hash Table for self avoiding random walks

• To: mathgroup at smc.vnet.net
• Subject: [mg88453] Hash Table for self avoiding random walks
• From: "jwmerrill at gmail.com" <jwmerrill at gmail.com>
• Date: Mon, 5 May 2008 06:17:32 -0400 (EDT)

Executive Summary:

Can I make a bunch of things that work like hash tables without
polluting the global scope?

Long winded Version:

I've been playing around with self avoiding random walks.  Generating
them efficiently requires a fast way of checking whether a given step
will intersect the set of previous steps, which is generally a sparse
subset of the underlying lattice.

Using a list of the previous steps isn't so great because searching it
for collisions is order the size of the list.  Using an array isn't so
great because it has predefined boundaries and because, as the
dimensionality increases, the size of the array goes like (side
length)^dimensions.

I think the ideal data structure is a hash table.  It takes constant
time to add new elements and constant time to check if a trial step
collides with a previous step, and there are no predefined
boundaries.  But it seems Mathematica doesn't have a true hash table.
SparseArray doesn't qualify because it wraps negative values and
complains if you look for something outside the boundaries.  Dispatch
doesn't qualify because (as far as I know) there's no way to add new
rules to an already created DispatchTables.

Googling <Mathematica Data Structures> led me to a nice article by
Daniel Lichtblau: http://library.wolfram.com/infocenter/Conferences/321/
, which shows how downvalues can be used in a similar way to hash
tables.  The article is from 1999, though, and I'm wondering if it's
still the state of the art.

The idea is simple.  If I have a walk that took steps {{1,1},{1,2},
{2,2}} then I make a function h:

h[{1,1}] = True;
h[{1,2}] = True;
h[{2,2}] = True;

My primary complaint with this technique is that it seems to require
giving your hash table a name with global scope.  What if I want to
make 100 different walks?  Do I have to give them all separate names?
I guess I could do something like h[10][1,1] = True;, but then I
always have to keep track of which walk I'm working on.  I'd rather
just be able to let them all be anonymous and stick them in a list.

Any ideas?  Here's my current best effort:

neighborhood[n_] :=
 With[{seed = ReplacePart[ConstantArray[0, n], 1 -> 1]},
  Join[Permutations[seed], Permutations[-seed]]]

availableSteps[{points_, visitedFunction_}] :=
 With[{steps = (Last[points] + #) & /@
     neighborhood[Dimensions[points][[2]]]},
  Select[steps, visitedFunction[#] =!= True &]]

takeStep[{points_, visitedFunction_}] :=
 With[{newStep =
    RandomChoice[availableSteps[{points, visitedFunction}]]},
  visitedFunction[Last[points]] = True;
  {Append[points, newStep], visitedFunction}]

Clear[trail];
{points, trail} =
  NestWhile[
   takeStep, {{{0, 0, 0}}, trail}, (Length[availableSteps[#]] > 0) &];

The part that I really don't like is the Clear[trail] part.

As an aside, although there is no documentation for HashTable, doing

FullForm[Dispatch[Table[n -> 1, {n, 4}]]]

gives

Dispatch[List[Rule[1,1],Rule[2,1],Rule[3,1],Rule[4,1]],List[HashTable[1,4,1,List[List[1,2,3],List[],List[4]]]]]

Is the feature set I want just hiding?

Regards,

JM

• Follow-Ups:
  • Re: Hash Table for self avoiding random walks
    • From: "W_Craig Carter" <ccarter@mit.edu>
  • Re: Hash Table for self avoiding random walks
    • From: "Jason Merrill" <jwmerrill@gmail.com>