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