(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