# [racket] Knuth's algorithm S

 From: Manfred Lotz (manfred.lotz at arcor.de) Date: Sun Mar 9 14:51:03 EDT 2014 Previous message: [racket] Knuth's algorithm S Next message: [racket] Knuth's algorithm S Messages sorted by: [date] [thread] [subject] [author]

```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)))

```

 Posted on the users mailing list. Previous message: [racket] Knuth's algorithm S Next message: [racket] Knuth's algorithm S Messages sorted by: [date] [thread] [subject] [author]