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