(define cp-reverse (lambda (lst) (letrec ([cpr (lambda (lst k) (cond ((null? lst) (k '())) (else (cpr (cdr lst) (lambda (v) (cons (car lst) (k v)))))))]) (cpr lst (lambda (v) v)))))
This is a rather classical example, indeed. Performance wise it's much slower than the reverse builtin in PLT-Scheme/Racket, still it's a lot faster than even more classical trivial implementations such as:
(define (sl-reverse lst) (cond ((null? lst) '()) (else (append (sl-reverse (cdr lst)) (list (car lst))))))
In fact the example relies on TCO modulo cons.
In order to test the whole thing in racket I used this snippet:
(define (print-times min max step) (for ([m (in-range min max step)]) (let ([lst (for/list ([i (in-range m)]) i)]) (time (reverse lst)) (time (cp-reverse lst)) (time (sl-reverse lst)))))
> (print-times 5000 10000 1000) cpu time: 0 real time: 10 gc time: 0 cpu time: 5 real time: 61 gc time: 0 cpu time: 1320 real time: 2088 gc time: 1099 cpu time: 1 real time: 0 gc time: 0 cpu time: 2 real time: 2 gc time: 0 cpu time: 463 real time: 493 gc time: 185 cpu time: 0 real time: 0 gc time: 0 cpu time: 2 real time: 21 gc time: 0 cpu time: 888 real time: 926 gc time: 505 cpu time: 0 real time: 0 gc time: 0 cpu time: 2 real time: 2 gc time: 0 cpu time: 2729 real time: 2766 gc time: 2235 cpu time: 0 real time: 0 gc time: 0 cpu time: 2 real time: 2 gc time: 0 cpu time: 2157 real time: 2227 gc time: 1522
No comments:
Post a Comment