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 <[email protected]>wrote: > 2012/5/28 Joe Gilray <[email protected]>: > > 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)) >
____________________ Racket Users list: http://lists.racket-lang.org/users
