Here is a benchmark for a few implementations of `range':
Nat Nat -> [Listof Nat]
(range 0 5) => (list 0 1 2 3 4 5)
(range 5 0) => (list 5 4 3 2 1 0)
One uses build-list, another uses sequences. I threw in an
implementation using an iterative build-list as well.
I was surprised the build-list version beat out sequences -- thoroughly,
with the iterative build-list being an improvement over the built in
recursive one.
David
$ mzc range-bench.scm
$ mzscheme range-bench.scm
(for ((j (in-range 5))) (range 0 1000000))
range-rbl: cpu time: 862 real time: 865 gc time: 387
range-ibl: cpu time: 905 real time: 905 gc time: 642
range-seq: cpu time: 2283 real time: 2289 gc time: 1138
(for ((j (in-range 50))) (range 0 100000))
range-rbl: cpu time: 518 real time: 519 gc time: 95
range-ibl: cpu time: 365 real time: 366 gc time: 116
range-seq: cpu time: 1560 real time: 1560 gc time: 443
(for ((j (in-range 500))) (range 0 10000))
range-rbl: cpu time: 357 real time: 358 gc time: 26
range-ibl: cpu time: 267 real time: 281 gc time: 18
range-seq: cpu time: 1153 real time: 1155 gc time: 54
(for ((j (in-range 5000))) (range 0 1000))
range-rbl: cpu time: 339 real time: 339 gc time: 12
range-ibl: cpu time: 258 real time: 258 gc time: 11
range-seq: cpu time: 1126 real time: 1156 gc time: 27
(for ((j (in-range 50000))) (range 0 100))
range-rbl: cpu time: 342 real time: 343 gc time: 9
range-ibl: cpu time: 264 real time: 265 gc time: 11
range-seq: cpu time: 1151 real time: 1151 gc time: 18
#lang scheme
;; Mini-benchmark for range Nat Nat -> [Listof Nat]
;; (range 0 5) => (list 0 1 2 3 4 5)
;; (range 5 0) => (list 5 4 3 2 1 0)
(define (it:build-list i f)
(let loop ([i (sub1 i)] [a empty])
(cond [(< i 0) a]
[else (loop (sub1 i)
(cons (f i) a))])))
;; using build-list
(define (range-rbl lo hi)
(if (>= hi lo)
(build-list (+ (- hi lo) 1) (lambda (i) (+ lo i)))
(build-list (+ (- lo hi) 1) (lambda (i) (- lo i)))))
;; same as above, but with iterative build-list
(define (range-ibl lo hi)
(if (>= hi lo)
(it:build-list (+ (- hi lo) 1) (lambda (i) (+ lo i)))
(it:build-list (+ (- lo hi) 1) (lambda (i) (- lo i)))))
;; using sequences
(define (range-seq L H)
(for/list ((i (if (>= H L)
(in-range L (+ H 1))
(in-range L (- H 1) -1)))) i))
(define ranges (list range-rbl range-ibl range-seq))
(define (run j i)
(printf "~a~n" `(for ((j (in-range ,j))) (range 0 ,i)))
(for-each
(lambda (r)
(printf "~a: " (object-name r))
(collect-garbage)
(time (void (for ((_ (in-range j))) (r 0 i)))))
ranges)
(newline))
#|
(run 5 1000000)
(run 50 100000)
...
(run 50000 100)
|#
(for ((i (in-range 5)))
(run (* 5 (expt 10 i))
(expt 10 (- 6 i))))
_________________________________________________
For list-related administrative tasks:
http://list.cs.brown.edu/mailman/listinfo/plt-dev
