[racket] idiomatic and fast

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
cs at csl.tc