[racket] a small programming exercise

On Thu, Oct 14, 2010 at 10:22 AM, Jay McCarthy <jay.mccarthy at gmail.com> wrote:
> I wrote mine in Racket then converted to Typed Racket.
Attached is a different version of Jay's original code, ported to
Typed Racket.  There are 4 changes to the runtime code:

1. use `vector-set!' and `vector-ref' instead of `dict-update!'
2. use `in-indexed' instead of `in-dict'
3. use `compose' with only two arguments, instead of N.
4. an assert to state that the result of `string->number' is an exact integer

I also had to add a type for `compose', now pushed.  There are also
many type annotations, which avoid the rest of the changes Jay made.

Hopefully, we'll have time to add the types for dict functions on
vectors in the near future.  `compose' will remain a 2-argument
function, though, unless someone has some very clever ideas for
extending the variable-arity polymorphism work.

As for timing, here's what I get.  For compile times:

[samth at punge:~ plt] time raco make benford-ut.rkt
real	0m0.458s
user	0m0.372s
sys	0m0.084s

[samth at punge:~ plt] time raco make benford.rkt
real	0m1.867s
user	0m1.708s
sys	0m0.120s

Approximately a factor of 3 in compilation time.  I think Jay's
numbers aren't right, since there's a big difference between the
'real' and 'user' times.

For run times, on this benchmark:
(define lst (build-list 100000 (λ (v) (random 11))))
(collect-garbage) (collect-garbage) (collect-garbage)
(time (sort-em (sk lst)))

[samth at punge:~ plt] racket benford.rkt
cpu time: 296 real time: 295 gc time: 8

[samth at punge:~ plt] racket benford-ut.rkt
cpu time: 292 real time: 292 gc time: 8

With minor noise, I think they're basically the same.  Unfortunately,
none of the optimizations we're doing have any impact on the
computation going on here, so it's not that surprising.  Vincent and I
have some ideas for optimizing this code, so stay tuned.
-- 
sam th
samth at ccs.neu.edu
-------------- next part --------------
A non-text attachment was scrubbed...
Name: benford.rkt
Type: application/octet-stream
Size: 1819 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20101014/a1a92917/attachment.obj>