[racket] a small programming exercise

I wrote mine in Racket then converted to Typed Racket.

Here is the final version:

http://github.com/jeapostrophe/exp/blob/master/benford.rkt

The changes to make it typed are pretty severe:

http://github.com/jeapostrophe/exp/commit/9487a13344360c93bf63a7859a2336a074f43cae

I had to drop using dictionaries, add lots of type annotations, drop
point free style on nums->digits, and drop the sorting function
because Typed Racket doesn't support polymorphic keyword arguments.

As far as the actual algorithm, I like it because it cleanly separates
the two jobs, although that makes it take 2n rather than n time
because I don't fuse the two loops. The first digit finder in the
final version is robust against negative numbers, decimals, fractions,
etc.

The changes needed for the Typed version don't reveal any errors. (The
closest case is that string->number can return false, but it would
never return false in this case.)

Let's see if Typed Racket made it any faster:

% time raco make benford.rkt
raco make benford.rkt  2.29s user 0.39s system 39% cpu 6.706 total
% time raco make benford-ut.rkt
raco make benford-ut.rkt  0.51s user 0.11s system 96% cpu 0.642 total

Compilation is almost 10 times slower.

% time racket -t benford.rkt
#t
racket -t benford.rkt  0.42s user 0.09s system 86% cpu 0.580 total
% time racket -t benford-ut.rkt
#t
racket -t benford-ut.rkt  0.20s user 0.05s system 95% cpu 0.267 total

Runtime is also slower. But maybe if I tried on larger lists, so I
tried a list of 100k random numbers between 0 and 10:

% time racket -t benford.rkt
racket -t benford.rkt  3.12s user 0.12s system 97% cpu 3.310 total
% time racket -t benford-ut.rkt
racket -t benford-ut.rkt  1.64s user 0.07s system 99% cpu 1.724 total

(Keep in mind both have to make the list)

Bummer. Looks like Typed is loser overall on this.

Jay

On Wed, Oct 13, 2010 at 10:10 PM, Shriram Krishnamurthi <sk at cs.brown.edu> wrote:
> Given: A list of numbers.  Assume integers (though it isn't necessary
> for the underlying issue).
>
> Task: To determine how often the first digit is 1, the first digit is
> 2, ..., the first digit is 9, and present as a table.  You may exploit
> DrRacket's pretty-printer, e.g., by using a list of lists:
>
> '((#\1 22.51539138082674)
>  (#\2 16.44678979771328)
>  (#\3 15.567282321899736)
>  (#\4 12.401055408970976)
>  (#\5 9.058927000879507)
>  (#\6 7.651715039577836)
>  (#\7 6.420404573438875)
>  (#\8 5.804749340369393)
>  (#\9 4.133685136323659))
>
> I leave the precise format of the output unstated so you're free to
> choose a clever representation; your answer should be at least as
> visually clear as the above.
>
> You should not mutate the original list, since it may be necessary for
> other computations.
>
> Smallest/tightest/cleanest/best?
>
> Shriram
>
> PS: Of course, this is to explore Benford's Law:
>
>    http://en.wikipedia.org/wiki/Benford's_law
>
>    which is the subject of my lecture tomorrow.  The above
>    distribution is from the size of the littoral zone (in acres) of
>    the lakes of Minnesota.
>
> PPS: If you really want to you can assume the data are actually in a
>     CSV file (as mine are -- thanks, Neil!), in case you can come up
>     with something even cleverer.
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/users
>



-- 
Jay McCarthy <jay at cs.byu.edu>
Assistant Professor / Brigham Young University
http://teammccarthy.org/jay

"The glory of God is Intelligence" - D&C 93