[racket] Racket style question

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
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120319/8cae83bf/attachment.html>