[racket] Help with filter-map
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))