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

Re: Hash Table for self avoiding random walks

• To: mathgroup at smc.vnet.net
• Subject: [mg88477] Re: Hash Table for self avoiding random walks
• From: David Bailey <dave at Remove_Thisdbailey.co.uk>
• Date: Tue, 6 May 2008 06:41:37 -0400 (EDT)
• References: <fvmn1l$8jn$1@smc.vnet.net>

jwmerrill at gmail.com wrote:
> 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
> 
Remember that the DownValue's in Daniel Lichtblau's technique can relate 
to a local variable:

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

etc.

David Bailey
http://www.dbaileyconsultancy.co.uk