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