[racket] Help with filter-map

Thanks Jens for explaining the filter-map idiom and for the fun code
example, very enlightening!

-Joe

On Mon, May 28, 2012 at 1:34 AM, Jens Axel Søgaard <jensaxel at soegaard.net>wrote:

> 2012/5/28 Joe Gilray <jgilray at gmail.com>:
> > I created some Racket solutions to ProjectEuler #71.  Below is one that
> uses
> > filter and map:
> >
> > (define (euler71c)
> >   (numerator (apply max (filter (λ (n) (> (/ 3 7) n)) (map (λ (n) (/
> (floor
> > (/ (* n 3) 7)) n)) (stream->list (in-range 2 1000000)))))))
> >
> > 1) I thought I might speed it up by using filter-map, but I cannot
> > understand how to do it.  I read the 1 line I could find in the reference
> > and it just doesn't help me
>
> The function filter-map keeps non-false elements.
> The idiom is therefore to use (and (> /37 n) n).
> The for and returns the last element only if all the preceding tests were
> true.
>
> > 2) The code above takes about 4x the time of a simple for loop
> > implementation.  What can I do to speed it up?
>
> Avoid allocation of unnecessary intermediate lists.
> Most often fold can be used for this purpose.
>
> Btw - when benchmarking in DrRacket - turn of debugging.
>
> I tried a few things. The results were:
>
> cpu time: 5174 real time: 5430 gc time: 3368
> cpu time: 4628 real time: 4859 gc time: 3311
> cpu time: 4122 real time: 4288 gc time: 2952
> cpu time: 3295 real time: 3401 gc time: 2318
> cpu time: 2674 real time: 2721 gc time: 1861
> cpu time: 2699 real time: 2746 gc time: 1843
>
> /Jens Axel
>
>
> #lang racket
>
> (define end 1000000)
>
> (define (euler71c)
>  (numerator
>   (apply max
>           (filter (λ (n) (> 3/7 n))
>                   (map (λ (n) (/ (floor (/ (* n 3) 7)) n))
>                        (stream->list (in-range 2 end)))))))
>
> (define (euler71d)
>  (numerator
>   (apply max
>          (filter (λ (n) (> 3/7 n))
>                   (map (λ (n) (/ (floor (/ (* n 3) 7)) n))
>                        (range 2 end))))))
>
> (define (euler71e)
>  (numerator
>   (apply max
>          (filter-map
>           (λ (m)
>             (define n (/ (floor (/ (* m 3) 7)) m))
>             (and (> 3/7 n) n))
>           (range 2 end)))))
>
> (define (euler71f)
>  (numerator
>   (foldl (λ (m max-so-far)
>            (define n (/ (floor (/ (* m 3) 7)) m))
>            (if (> 3/7 n)
>                (max n max-so-far)
>                max-so-far))
>          0
>          (range 2 end))))
>
> (define (euler71g)
>  (numerator
>   (for/fold ([max-so-far 0]) ([m (in-range 2 end)])
>     (define n (/ (floor (/ (* m 3) 7)) m))
>     (if (> 3/7 n) (max n max-so-far) max-so-far))))
>
> (define (euler71h)
>  (define max-so-far 0)
>  (for ([m (in-range 2 end)])
>    (define n (/ (floor (/ (* m 3) 7)) m))
>    (set! max-so-far
>          (if (> 3/7 n) (max n max-so-far) max-so-far)))
>  (numerator max-so-far))
>
> (define (test)
>  (let ([old-end end])
>    (set! end 10)
>    (begin0
>      (list (equal? (euler71c) (euler71d))
>            (equal? (euler71d) (euler71e))
>            (equal? (euler71e) (euler71f))
>            (equal? (euler71f) (euler71g))
>            (equal? (euler71g) (euler71h)))
>      (set! end old-end))))
>
> (define (benchmark-one f)
>  (collect-garbage)
>  (time (begin (f) (void))))
>
> (define (benchmark)
>  (benchmark-one euler71c)
>  (benchmark-one euler71d)
>  (benchmark-one euler71e)
>  (benchmark-one euler71f)
>  (benchmark-one euler71g)
>  (benchmark-one euler71h))
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120528/0df54081/attachment-0001.html>