[racket] Racket style question
Oops... (still learning, Thanks Robby) ... New results run under Racket.exe:
(define (pythagorean-triple n)
(let loop-ab ([a 1] [b 2])
(define c (- n a b))
(cond [(right-triangle? a b c) (list a b c)]
[(>= a (ceiling (/ n 3))) '()]
[(<= c b) (loop-ab (add1 a) (+ a 2))]
[else (loop-ab a (add1 b))])))
Ave cpu time = 0.46 seconds
(define (pythagorean-triple2 n)
(for*/first ([a (in-range 1 (ceiling (/ n 3)))]
[b (in-range (add1 a) (ceiling (/ (- n a) 2)))]
[c (in-value (- n a b))]
#:when (and (< b c)
(right-triangle? a b c)))
(list a b c)))
Ave cpu time = 0.69 seconds
(define (pythagorean-triple4 n)
(for*/or ([a (in-range 1 (ceiling (/ n 3)))]
[b (in-range (add1 a) (ceiling (/ (- n a) 2)))])
(define c (- n a b))
(and (right-triangle? a b c) (list a b c))))
Ave cpu time = 0.46 seconds
Notes:
- pre-defining a-limit didn't help any algorithm
- trying to further limit b slowed down the first algorithm a small amount
- DrRacket does add quite a bit of overhead
-Joe
On Mon, Mar 19, 2012 at 11:39 AM, Robby Findler <robby at eecs.northwestern.edu
> wrote:
> Apologies if this is old news, but if you're running timing tests, be
> sure to run them in 'racket', from a command-line, not in DrRacket.
> DrRacket is doing lots of stuff at the same time as running your
> program that can make measurements significantly less accurate.
>
> Robby
>
> On Mon, Mar 19, 2012 at 1:34 PM, Joe Gilray <jgilray at gmail.com> wrote:
> > Hi again Rodolfo,
> >
> > After a some mods, I ran several trials with n = 10000 on my ancient
> laptop
> > and got the following results:
> >
> > (define (pythagorean-triple n)
> > (define a-limit (ceiling (/ n 3)))
> > (let loop-ab ([a 1] [b 2])
> > (define c (- n a b))
> > (cond [(right-triangle? a b c) (list a b c)]
> > [(>= a a-limit) '()]
> > [(<= c b) (loop-ab (add1 a) (+ a 2))]
> > [else (loop-ab a (add1 b))])))
> >
> > Ave cpu time = 3.90 seconds (note that trying to limit b slowed down the
> > performance considerably, but pre-defining a-limit helped a little
> compared
> > to not limiting a at all)
> >
> > (define (pythagorean-triple2 n)
> > (for*/first ([a (in-range 1 (ceiling (/ n 3)))]
> > [b (in-range (add1 a) (ceiling (/ (- n a) 2)))]
> > [c (in-value (- n a b))]
> > #:when (and (< b c)
> > (right-triangle? a b c)))
> > (list a b c)))
> >
> > Ave cpu time = 5.25 seconds (pre-defining a-limit didn't improve
> performance
> > like it did above)
> >
> > (define (pythagorean-triple3 n)
> > (for*/or ([a (in-range 1 n)]
> > [b (in-range a n)]
> > #:when (< (* 2 b) (- n a)))
> > (define c (- n a b))
> > (and (right-triangle? a b c) (list a b c))))
> >
> > Ave cpu time = 4.90 seconds
> >
> > (define (pythagorean-triple4 n)
> > (for*/or ([a (in-range 1 (ceiling (/ n 3)))]
> > [b (in-range (add1 a) (ceiling (/ (- n a) 2)))])
> > (define c (- n a b))
> > (and (right-triangle? a b c) (list a b c))))
> >
> > Ave cpu time = 2.50 seconds (!!, note that pre-defining a-limit didn't
> > improve performance here either)
> >
> > I'm learning a lot from these examples. I'd love to see other idioms as
> > well.
> >
> > Thanks,
> > -Joe
> >
> > On Mon, Mar 19, 2012 at 12:44 AM, Rodolfo Carvalho <rhcarvalho at gmail.com
> >
> > wrote:
> >>
> >> On Mon, Mar 19, 2012 at 04:35, Joe Gilray <jgilray at gmail.com> wrote:
> >>>
> >>> Thanks Rodolfo and Eli for the education, very elegant solutions.
> >>>
> >>> I really like the clever use of the "(and (right-triangle? a b c)
> (list a
> >>> b c))))" idiom.
> >>>
> >>> I had to look up in-value... unfortunately the manual is a bit sparse
> >>> there, but I got the gift by running some examples... thanks.
> >>>
> >>> After going "D'oh" about the infinite loop, here is the code I ended up
> >>> with:
> >>>
> >>> (define (pythagorean-triple n)
> >>> (let loop-ab ([a 1] [b 2])
> >>> (define c (- n a b))
> >>> (cond [(>= a n) '()]
> >>> [(<= c b) (loop-ab (add1 a) (+ a 2))]
> >>> [(right-triangle? a b c) (list a b c)]
> >>> [else (loop-ab a (add1 b))])))
> >>>
> >>> I noticed that the sequence-based solutions are quite a bit slower than
> >>> the code above probably because they don't short-cut on (<= c b), is
> there
> >>> an elegant way to speed them up?
> >>>
> >>
> >> Before you asked I wrote this:
> >>
> >> ; by Rodolfo Carvalho
> >> (define (pythagorean-triple/alt n)
> >> (for*/first ([a (in-range 1 (ceiling (/ n 3)))]
> >> [b (in-range (add1 a) (ceiling (/ (- n a) 2)))]
> >> [c (in-value (- n a b))]
> >> #:when (and (< b c)
> >> (right-triangle? a b c)))
> >> (list a b c)))
> >>
> >>
> >> ; by Eli on the mailing list, modified by Rodolfo
> >> (define (pythagorean-triple/alt2 n)
> >> (for*/or ([a (in-range 1 n)]
> >> [b (in-range (add1 a) n)]) ; start from `a+1' instead of
> `a'.
> >> (define c (- n a b))
> >> (and (< b c) (right-triangle? a b c) (list a b c)))) ; added `(< b
> c)'
> >> check.
> >>
> >>
> >>
> >> And counted how many times they call right-triangle -- the same number
> of
> >> times.
> >> Indeed your (first) solution with let loops seems slightly faster, but
> not
> >> by a significant margin in my experiments.
> >>
> >> I didn't take the time to analyze it much, but looking at the code
> >> expansion using the Macro Stepper suggested that the for macros
> generate a
> >> lot more code to be executed than the nested lets.
> >>
> >>
> >> []'s
> >>
> >> Rodolfo Carvalho
> >>
> >>
> >>
> >
> >
> > ____________________
> > Racket Users list:
> > http://lists.racket-lang.org/users
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120319/903a38b2/attachment.html>