On Sat, May 2, 2009 at 7:37 PM, namekuseijin <namekusei...@gmail.com> wrote: > 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... >
heh, should not have benchmarked it while on DrScheme environment: namekusei...@nameku:~/dev/scheme$ mzc range-bench.scm namekusei...@nameku:~/dev/scheme$ mzscheme range-bench.scm (for ((j (in-range 5))) (range 0 1000000)) range-rbl: cpu time: 728 real time: 732 gc time: 452 range-ibl: cpu time: 416 real time: 424 gc time: 236 range-seq: cpu time: 1224 real time: 1285 gc time: 440 range-nmk: cpu time: 488 real time: 503 gc time: 236 (for ((j (in-range 50))) (range 0 100000)) range-rbl: cpu time: 456 real time: 458 gc time: 196 range-ibl: cpu time: 204 real time: 207 gc time: 40 range-seq: cpu time: 952 real time: 1016 gc time: 180 range-nmk: cpu time: 292 real time: 303 gc time: 36 (for ((j (in-range 500))) (range 0 10000)) range-rbl: cpu time: 284 real time: 285 gc time: 32 range-ibl: cpu time: 180 real time: 181 gc time: 8 range-seq: cpu time: 804 real time: 851 gc time: 28 range-nmk: cpu time: 260 real time: 271 gc time: 12 (for ((j (in-range 5000))) (range 0 1000)) range-rbl: cpu time: 268 real time: 269 gc time: 12 range-ibl: cpu time: 176 real time: 176 gc time: 8 range-seq: cpu time: 836 real time: 836 gc time: 8 range-nmk: cpu time: 268 real time: 265 gc time: 4 (for ((j (in-range 50000))) (range 0 100)) range-rbl: cpu time: 276 real time: 274 gc time: 8 range-ibl: cpu time: 180 real time: 181 gc time: 4 range-seq: cpu time: 856 real time: 858 gc time: 20 range-nmk: cpu time: 272 real time: 271 gc time: 8 What's the cause of so much difference? Going through mzscheme, the manually named-let-written build-list really beats the socks of builtin build-list! _________________________________________________ For list-related administrative tasks: http://list.cs.brown.edu/mailman/listinfo/plt-dev
