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