[racket] Knuth's algorithm S

From: Manfred Lotz (manfred.lotz at arcor.de)
Date: Sun Mar 9 12:34:04 EDT 2014

Hi there, 
I had a look at the implementations of Knuth's algorithm S at rosetta
code: http://rosettacode.org/wiki/Knuth's_algorithm_S#Racket

What baffles me is the fact that the Racket version is so slow. Running
some sample on my laptop I have:

Ruby: ruby kas.rb  0.57s user 0.01s system 99% cpu 0.574 total
Perl: perl kas.pl  1.24s user 0.00s system 99% cpu 1.244 total
Racket: racket kas.rkt  2.68s user 0.01s system 99% cpu 2.700 total

I tried to improve but didn't get a significant improvement.

Finally, I found why it is slow. In the Racket sample there is:

 (when (< (random) (/ n count))
              (vector-set! vec (random n) item))

which I changed to

 (when (< (* count (random)) n)
              (vector-set! vec (random n) item))


Now I have:
racket kasX.rkt  0.36s user 0.01s system 99% cpu 0.372 total

This far slower than compiled languages but I think it
is quite ok.


The slowness seems to have to do with rational and converting from
rational to real, just my guess.

Question: Is the way I improved it the right way, or is there a better
more idiomatic approach?

-- 
Manfred






Posted on the users mailing list.