Seems to me you're measuring consing. I'm not really a fan of
creating intermediary lists, I enjoy iterators more. I have my own
version of range, here simplified:
; returns an iterator for given range
; given an initial result and a reducer function, will apply it each iteration
(define (range from to)
(let ((> (if (> from to) < >))
(+ (if (> from to) - +)))
(lambda (res reducer)
(let loop ((i from) (r res))
(if (> i to) r
(loop (+ i 1) (reducer i r)))))))
So, I can:
((range 10 1) '() cons)
to create a list from 1 to 10 (cons builds a reverse list)
or simply
((range 1 10) 0 +)
to sum it up, without creating intermediary lists.
or even
((range 1 10) 0 (lambda (i o) (if (odd? i) (+ i o) o)))
to sum only the odds. Of course, I have a version of filter to work
with iterators. :)
I added it to the benchmark by adding a little twist: it now builds a
list by consing too.
(define (range-nmk from to)
(let ((> (if (> from to) < >))
(+ (if (> from to) - +)))
((lambda (res reducer)
(let loop ((i from) (r res))
(if (> i to) r
(loop (+ i 1) (reducer i r))))) '() cons)))
(define ranges (list range-rbl range-ibl range-seq range-nmk))
on DrScheme:
(for ((j (in-range 5))) (range 0 1000000))
range-rbl: cpu time: 852 real time: 851 gc time: 332
range-ibl: cpu time: 1332 real time: 1334 gc time: 88
range-seq: cpu time: 1052 real time: 1055 gc time: 212
range-nmk: cpu time: 704 real time: 706 gc time: 80
(for ((j (in-range 50))) (range 0 100000))
range-rbl: cpu time: 588 real time: 585 gc time: 68
range-ibl: cpu time: 1300 real time: 1301 gc time: 20
range-seq: cpu time: 908 real time: 908 gc time: 72
range-nmk: cpu time: 652 real time: 653 gc time: 20
(for ((j (in-range 500))) (range 0 10000))
range-rbl: cpu time: 544 real time: 544 gc time: 28
range-ibl: cpu time: 1300 real time: 1297 gc time: 12
range-seq: cpu time: 864 real time: 863 gc time: 24
range-nmk: cpu time: 644 real time: 644 gc time: 12
(for ((j (in-range 5000))) (range 0 1000))
range-rbl: cpu time: 544 real time: 543 gc time: 20
range-ibl: cpu time: 1300 real time: 1300 gc time: 8
range-seq: cpu time: 864 real time: 864 gc time: 20
range-nmk: cpu time: 648 real time: 645 gc time: 8
(for ((j (in-range 50000))) (range 0 100))
range-rbl: cpu time: 568 real time: 565 gc time: 20
range-ibl: cpu time: 1328 real time: 1328 gc time: 12
range-seq: cpu time: 900 real time: 902 gc time: 20
range-nmk: cpu time: 664 real time: 664 gc time: 12
The pure recursive way beats it, except for a fairly high range. I
wonder why...
_________________________________________________
For list-related administrative tasks:
http://list.cs.brown.edu/mailman/listinfo/plt-dev
