[racket] Knuth's algorithm S

On Sun, 9 Mar 2014 16:44:06 -0400
Matthias Felleisen <matthias at ccs.neu.edu>
wrote:

> 
> Consider moving the defines into main, and then run main: on my Mac,
> this drives down the time by another 10%+: 
> 

Hm, interesting. Didn't make a difference on my Linux system.

Anyway, overall I'm quite satisfied. I learned that it is important to
pay attention to rational/real number issues (at least in cases where
something runs so often).


-- 
Manfred


> #! /bin/sh
> #|
> exec racket -t "$0" ${1+"$@"}
> |#
> 
> #lang racket/base
> 
> (provide main)
> 
> (require racket/function)
> 
> (define (main)
>   (define (s-of-n-creator n)
>     [define count 0] ; 'i' in the description
>     [define vec (make-vector n)] ; store the elts we've seen so far
>     (lambda (item)
>       (cond
>         [(< count n)
>          (vector-set! vec count item)
>          (set! count (+ count 1))]
>         [else
>          (set! count (+ count 1))
>          (when (< (* count (random)) n)
>            (vector-set! vec (random n) item))])
>       vec))
>   
>   (define counts (build-vector 10 identity))
>   
>   (for ([iter (in-range 0 100000)])
>     (let ([s-of-n (s-of-n-creator 3)]) 
>       (define v 
>         (for/last ([digit (in-range 0 10)])
>           (s-of-n digit)))
>       (for ([d (in-vector v)])
>         (vector-set! counts d (add1 (vector-ref counts d))))))
>   
>   (for ([d (in-range 0 10)])
>     (printf "~a ~a~n" d (vector-ref counts d))))
> 
> ; (require optimization-coach)
> ; optimization-coach-profile 
> (time (main))
> 
> 
> 
> 
> On Mar 9, 2014, at 2:51 PM, Manfred Lotz wrote:
> 
> > On Sun, 09 Mar 2014 14:34:05 -0400
> > Neil Van Dyke <neil at neilvandyke.org> wrote:
> > 
> >> Manfred Lotz wrote at 03/09/2014 01:13 PM:
> >>> There is a certain way the
> >>> algorithm should be implemented (given at the top of the page).
> >>> 
> >> 
> >> I haven't traced through the algorithm completely (and I have to
> >> run out the door now), but looks like you might be able to replace
> >> the "(vector-copy vec)" with "vec".  (At least for purposes of
> >> this benchmark of 100,000 iterations; for a reusable library, you
> >> might not do it that way, nor the way that rosettacode.org
> >> prescribes.)
> >> 
> >> On my computer, eliminating that one "vector-copy" from the code
> >> drops run time down to 0.6 of what it is with your change.  The
> >> output distribution looks the same to me.
> >> 
> > 
> > Yes. Here is my current improved version which runs in 0.216 total
> > which is a big improvement to 0.372 secs.
> > 
> > #lang racket/base
> > 
> > (require racket/function)
> > (require racket/vector)
> > 
> > (define (s-of-n-creator n)
> >  (let* ([count 0] ; 'i' in the description
> >         [vec (make-vector n)]) ; store the elts we've seen so far
> >    (lambda (item)
> >      (if (< count n)
> >          ; we're not full, so, kind of boring
> >          (begin
> >            (vector-set! vec count item)
> >            (set! count (+ count 1)))
> >          ; we've already seen n elts; fun starts
> >          (begin
> >            (set! count (+ count 1))
> >            (when (< (* count (random)) n)
> >              (vector-set! vec (random n) item))))
> >      vec)))
> > 
> > (define counts (build-vector 10 identity))
> > 
> > (for ([iter (in-range 0 100000)]) ; trials
> >  (let ([s-of-n (s-of-n-creator 3)]) ; set up the chooser
> >    (for ([d (in-vector ; iterate over the chosen digits
> >              (for/last ([digit (in-range 0 10)]) ; loop through the
> > digits 
> >                  (s-of-n digit)))]) ; feed them in
> >      (vector-set! counts d (add1 (vector-ref counts d)))))) 
> > 
> > (for ([d (in-range 0 10)])
> >  (printf "~a ~a~n" d (vector-ref counts d)))
> > 
> > 
> > 
> > ____________________
> >  Racket Users list:
> >  http://lists.racket-lang.org/users
> 
> 
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users
>