[racket] idiomatic and fast
I don't know if I could ever be a resource on "most idiomatic",
especially since I basically never use any of the for/et ceteras but
this feels reminiscent of "The Little Schemer" to me (except for the
internal define instead of letrec):
(define (make-triangles to-n)
(define (next-triangle last-sum current-number)
(if (> current-number to-n)
empty
(let ((new-sum (+ last-sum current-number)))
(cons new-sum (next-triangle new-sum (add1 current-number))))))
(next-triangle 0 1))
If for some reason I was worried about all the leftover conses---I try
not to worry about these things unless I have to---I could make it
totally tail-recursive at the cost of doing one big reverse at the
end:
(define (make-triangles-2 to-n)
(define (next-triangle last-sum current-number results-so-far)
(if (> current-number to-n)
(reverse results-so-far)
(let ((new-sum (+ last-sum current-number)))
(next-triangle new-sum
(add1 current-number)
(cons new-sum results-so-far)))))
(next-triangle 0 1 empty))
********
> (define-syntax-rule (my-time expression)
(begin
(collect-garbage)(collect-garbage)(collect-garbage)
(time expression)))
> (let ((n 50000))
(collect-garbage)(collect-garbage)(collect-garbage)
(let ((one (my-time (make-triangles n)))
(two (my-time (make-triangles-2 n)))
(three (my-time (for/list ([i (in-range 2 (+ n 2))])
(for/sum ([j (in-range i)]) j)))))
(and (equal? one two) (equal? two three))))
cpu time: 47 real time: 47 gc time: 0
cpu time: 15 real time: 16 gc time: 0
cpu time: 12984 real time: 14375 gc time: 140
#t
Deren
On Sat, Apr 28, 2012 at 3:54 PM, Joe Gilray <jgilray at gmail.com> wrote:
> Hi,
>
> I'm trying to come up with the most idiomatic way to generate triangle
> numbers that is also fast:
>
> (for/list ([i (in-range 2 22)]) (for/sum ([j (in-range i)]) j))
>
> works but is slow because it regenerates the sums each time
>
> (define s 0) (for/list ([i (in-range 1 21)]) (set! s (+ s i)) s)
>
> is fast, but ugly.
>
> How do I keep the sum in an idiomatic fashion?
>
> Thanks,
> -Joe
>
> ____________________
> Racket Users list:
> http://lists.racket-lang.org/users
>