[racket] a small programming exercise

From: Jay McCarthy (jay.mccarthy at gmail.com)
Date: Thu Oct 14 11:58:03 EDT 2010

I timed the process not the function to account for loading the typed runtime. 


Sent from my iPhone

On Oct 14, 2010, at 9:51 AM, Sam Tobin-Hochstadt <samth at ccs.neu.edu> wrote:

> 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
> <benford.rkt>

Posted on the users mailing list.