[racket] Help with filter-map
Joe Gilray
Neil Van Dyke
1000000))" is constructing a list of approx. 1 million elements just to
count a number by 1. Counting a number by 1 can instead be done by: (+
1 number)
The fancy iterators like "for" can do secret tricks to make things like
"(in-range 2 1000000)" be reasonable to use in Racket. But
"stream->list" cannot do these secret tricks, since it really does
construct a non-lazy list of approx. a million elements.
Two alternatives:
1. One can use Racket like a mathematician who uses umpteen operators to
make umpteen lists of arbitrary size, since everything is declarative
and functional and pure and free. Performance is not an issue, since
the universe of this mathematician has no dimension of time.
2. One can care about runtime performance, and treat Racket to a large
extent as a conventional algorithmic programming language for the
conventional architecture. I think this is easier to learn if one does
things like: (1) mothballs Project Euler and focuses on problems better
suited to learning the fundamentals of Racket; (2) avoids using Racket
sequences and iterators and fancy list functions and such, until
understanding how one would do it efficiently without those things; and
(3) is skeptical of anything that would look good to a mathematician,
since the way of the mathematician is the way of lies.
BTW, line breaks would improve the readability of the code, by visually
exposing more of the nesting structure.
Neil V.
____________________
Racket Users list:
http://lists.racket-lang.org/users
Jens Axel Søgaard
> 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))