[racket] a small programming exercise
I timed the process not the function to account for loading the typed runtime.
Jay
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>