[racket] Racket style question
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
>