On 28/04/12 22:54, Joe Gilray wrote:
>
> (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?
>
Joe
Here are some solutions that I would consider more idiomatic. And fast
enough.
Your first (Slow) solution is asymptotically slower than the (fast and
ugly) solution . The time taken by slow is O(n^2). None of these
solutions have this problem.
Solution 1:
Let foldl keep the total for you
(define (first-n-triangle-numbers n)
(rest (reverse (foldl (lambda (l r) (cons (+ l (first r)) r)) (list 0)
(rest (build-list (add1 n) (lambda (x) x)))))))
This is blisteringly fast - it generates 20000 triangle numbers as fast
as your "ugly" code.
Solution 2:
Use the formula discovered by the schoolboy Gauss:
(define (first-n-triangle-numbers-formula n)
(map (lambda (n) (/ (* n (add1 n)) 2)) (rest (build-list n
(lambda(x) x)))))
I was surprised to find that this seems to be twice as slow as solution
1. Not really a significant difference, though, and easier to understand
than 1.
Solution 3:
Make an infinite list of triangle numbers in lazy racket. Not very fast,
but very idiomatic, and it does make a list of *all* the triangle numbers.
About 20 times as slow as solution 1, but still O(n)
#lang lazy
(define integers (cons 1 (map add1 integers)))
(define triangle-numbers (cons 1 (map + (rest integers) triangle-numbers)))
You need to evaluate the line below to actually see the list
(time (!!list(take 20000 triangle-numbers)))
Try it a second time and get a (pleasant) surprise.
; it goes a bit (I mean a lot) faster the second time
(time (!!list(take 20000 triangle-numbers)))
Chris
--
Chris Stephenson
c...@csl.tc
____________________
Racket Users list:
http://lists.racket-lang.org/users
