[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>