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