[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>