Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2008

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

Search the Archive

Re: Hash Table for self avoiding random walks

  • To: mathgroup at smc.vnet.net
  • Subject: [mg88499] Re: Hash Table for self avoiding random walks
  • From: Szabolcs Horvát <szhorvat at gmail.com>
  • Date: Tue, 6 May 2008 06:45:43 -0400 (EDT)
  • Organization: University of Bergen
  • References: <fvmn1l$8jn$1@smc.vnet.net>

jwmerrill at gmail.com wrote:
> 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.
> 

Your code looks good to me.  You can use Module[] to localize 'trail', 
this way it won't be necessary to use Clear[].

Here's a slight modification that runs ~4x faster on my machine:

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

step[visited_][pt_] := With[
   {steps =
     Select[(pt + #) & /@
       neighbourhood@Length[pt], ! ValueQ[visited[#]] &]},
   If[steps =!= {},
    With[{next = RandomChoice[steps]},
     visited[next] = True;
     next
     ],
    Null]
   ]

Module[{trail},
  Most@NestWhileList[step[trail], {0, 0, 0}, # =!= Null &]

I've thrown this together quickly, so it's a bit messy ... sorry about 
that (especially about merging takeStep and availableSteps, which serves 
no purpose in this case).

The two main optimizations are caching the result of neighbourhood[], 
and using NestWhileList instead of NestWhile + Append.  I have not timed 
the parts of the function separately, but I suspect that the speedup is 
due to the latter change.

I hope this helps,
Szabolcs



  • Prev by Date: graph plot
  • Next by Date: Re: orthonormal eigenvectors
  • Previous by thread: Re: Hash Table for self avoiding random walks
  • Next by thread: Re: Hash Table for self avoiding random walks