[plt-scheme] random walk
First, I'd like to thank all who tried to help me previously with this.
Unfortunately I still didn't manage to fix my macro mess, so I have tried again
with functions.
Matthias Felleisen wrote:
>
> Do you want this function? I don't see the need for a macro.
Yes, this code does what I need, but it doesn't do it fast enough.
> #lang scheme
I commented this out, since I don't know how to run with it.
>
> ;; Nat Nat -> Nat
> ;; compute L2 distance for all random walks of depth dpt in n-space
> (define (walk n depth)
> (define O (make-vector n 0))
> (define Ds (deltas n))
> (let step ((ld 0) (p O))
> (if (>= ld depth)
> (L2 p)
> (apply + (map (lambda (d) (step (+ ld 1) (v+ p d))) Ds)))))
>
> ;; (Vectorof Nat) -> Nat
> (define (L2 p)
> (apply + (map sqr (vector->list p))))
>
> ;; Nat -> (Listof (Vectorof {0|+1|-1}))
> (define (deltas n)
> (define (mk+1 i) (lambda (j) (if (= i j) +1 0)))
> (define (mk-1 i) (lambda (j) (if (= i j) -1 0)))
> (apply append
> (build-list n (lambda (i)
> (list (build-vector n (mk+1 i))
> (build-vector n (mk-1 i)))))))
>
> ;; (Vectorof Nat) (Vector Nat) -> (Vector Nat)
> (define (v+ u v)
> ;; I am sure there's some for/vector somewhere, I can't find it
> (list->vector (for/list ((x u) (y v)) (+ x y))))
>
> ;;
I added:
(define (main depth)
(pretty-print (/ (walk 2 depth) (expt 4 depth))))
Then I ran like so:
mzscheme -f felleisen-walk.scm -e "(time (main 10))"
10
cpu time: 1940 real time: 1956 gc time: 75
The following code:
(define (fast-squared-L2-norm-2 x y)
(+ (* x x) (* y y)))
(define (fast-walk-2 depth)
(let step ((d 0) (x 0) (y 0) #;(z 0))
(cond ((< d depth)
(let ((d+1 (+ d 1)))
(+ (step d+1 (+ x 1) y)
(+ (step d+1 (- x 1) y)
(+ (step d+1 x (+ y 1))
(step d+1 x (- y 1)) )))))
(else
(fast-squared-L2-norm-2 x y)))))
is specific to dimension 2 but also much faster:
$ mzscheme -e "(define pp pretty-print)" -f randomwalk.scm -e "(time (main 10))"
10
cpu time: 59 real time: 59 gc time: 0
I also have an abstract version that runs in any dimension that runs 10 times as
slow as my fast version and 3 times faster than your version. There are
certainly some areas in my abstract version which I am extremely unhappy about
that account for a lot of consing.
Anyway, I'm interested in code that runs as fast as my fast code above, but is
also able to work with arbitrary dimension, such that I do not have to duplicate
my code for each dimension that I am interested in. I would be very happy if I
could do that by optimizing some abstract version that uses only functions by
eliminating consing and non-tail recursion, but currently it seems to me that
only a macro that generates the fast code given a particular dimension will give
maximum speed.
Further I would like to note that preliminary testing seems to indicate that
plt-scheme is quite competitive with other fast implementations that I have
tried for my current code (unlike say gauche (3-4 times slower) or scheme48 (4
times slower than gauche)). Previous testing had shown plt to be (only)
medium-fast, so I am pleasantly surprised.
I have attached a file with my slow and fast implementations (no macros yet).
You can switch between the implementations in the main function at the bottom.
Thanks,
Marijn
> -----------------------------------------------------------------------------
>
> (require test-engine/scheme-tests)
>
> ;; deltas
> (check-expect (deltas 0) '())
> (check-expect (deltas 1) (list (vector +1) (vector -1)))
> (check-expect
> (deltas 2) (list (vector +1 0) (vector -1 0) (vector 0 +1) (vector 0 -1)))
>
> ;; v+
> (check-expect (v+ #3(2 3 0) #3(-1 0 0)) #3(1 3 0))
>
> ;; L2
> (check-expect (L2 #3(2 3 0)) 13)
>
> ;; walk:
> ;; add your favorite test here
>
> (test)
>
>
>
>
> On May 29, 2009, at 11:08 AM, Marijn Schouten (hkBst) wrote:
>
>> Hi,
>>
>> I'm trying to write a macro that writes a function that sums the
>> L2-lengths of
>> all (random) walks of depth d on a square grid of dimension DIM. In
>> dimension 2
>> that function should look like this:
>>
>>
>> (define (walk depth)
>> (let step ((d 0) (x 0) (y 0) #;(z 0))
>> (cond ((< d depth)
>> (let ((d+1 (+ d 1)))
>> (+
>> (step d+1 (+ x 1) y)
>> (+
>> (step d+1 (- x 1) y)
>> (+ (step d+1 x (+ y 1))
>> (step d+1 x (- y 1))) ))))
>> (else
>> (+ (* x x) (* y y)) ) )))
>>
>>
>> (walk d) starts at the origin, (x,y) = (0,0), and recursively walks a
>> step in
>> all 2DIM directions, returning the L2-length when depth d is reached
>> and summing
>> all those lengths. It is not hard to prove that (walk depth) is equal
>> to (expt
>> (* 2 (DIM)) depth) but this random walk length summer is only the
>> starting point
>> for doing more interesting things.
>>
>> I'm looking for a macro that will write the `walk' function given the
>> dimension.
>>
>> Attached is an attempt that I cannot seem to get working.
>>
>> Thanks,
>>
>> Marijn
--
If you cannot read my mind, then listen to what I say.
Marijn Schouten (hkBst), Gentoo Lisp project, Gentoo ML
<http://www.gentoo.org/proj/en/lisp/>, #gentoo-{lisp,ml} on FreeNode
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: randomwalk.scm
URL: <http://lists.racket-lang.org/users/archive/attachments/20090611/928695d5/attachment.ksh>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 261 bytes
Desc: OpenPGP digital signature
URL: <http://lists.racket-lang.org/users/archive/attachments/20090611/928695d5/attachment.sig>