[racket] Knuth's algorithm S

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

#! /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