Using accumulator+reverse won't really improve the runtime at all.
The thing is, Racket's "stack" is a list of continuations. I don't see
how explicitly keeping the "stack" in an accumulator would help. Stack
overflow won't be a problem since the "stack" is a list on the heap, and
unless memory runs out you wont overflow. Obviously memory can run out
if the accumulator gets too big also.
Stupid benchmark:
#lang racket
(define (list-incr/direct lst)
(cond
[(empty? lst) empty]
[else (cons (add1 (car lst))
(list-incr/direct (cdr lst)))]))
(define (list-incr/acc lst (acc empty))
(cond
[(empty? lst) (reverse acc)]
[else (list-incr/acc (cdr lst)
(cons (add1 (car lst))
acc))]))
(define huge-list
(build-list 50000 identity))
(time
(for ([i 20])
(list-incr/direct huge-list))
(collect-garbage)
(collect-garbage)
(collect-garbage))
(time
(for ([i 20])
(list-incr/acc huge-list))
(collect-garbage)
(collect-garbage)
(collect-garbage))
> cpu time: 1496 real time: 1495 gc time: 1368
> cpu time: 1464 real time: 1465 gc time: 1368
I think that tail recursion doesn't help at all, and introduces
conceptual overhead. Racket doesn't use the stack, and converts to
continuation-passing, which is surprise-surprise *tail recursive* at
runtime anyway.
On Sun, 2014-03-16 at 17:30 -0400, Sam Tobin-Hochstadt wrote:
> Basically, avoiding growing the stack when building a list, by
> compiling this program:
>
> (define (list-id l)
> (if (null? l) l
> (cons (car l) (list-id (cdr l)))))
>
> into this one:
>
> (define (list-id* l acc)
> (if (null? l)
> (set-cdr! acc null)
> (let ([p (cons (car l) #f)])
> (set-cdr! acc p)
> (list-id (cdr l) p))))
>
> There's a pretty good discussion on Wikipedia:
> http://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons
>
> Note that this doesn't run in constant space, since we're allocating a
> pair at each step, but it changes the complexity from 2n to n.
>
> Sam
>
>
> On Sun, Mar 16, 2014 at 5:13 PM, Matthias Felleisen
> <matth...@ccs.neu.edu> wrote:
> >
> > What does tail-recursion modulo cons mean?
> >
> >
> > On Mar 16, 2014, at 3:38 PM, Sam Tobin-Hochstadt wrote:
> >
> >> On Sun, Mar 16, 2014 at 2:55 PM, Patrick Useldinger
> >> <uselpa.l...@gmail.com> wrote:
> >>>
> >>>
> >>> My questions are:
> >>>
> >>> (1) Is Racket "tail-recursive modulo cons"? If not, is there a reason for
> >>> this?
> >>
> >> Racket is not "tail-recursive modulo cons".
> >>
> >>> (2) Is the last example "reverse free" or does it use reverse under the
> >>> hood?
> >>
> >> `for/list` uses `reverse` internally -- you can see for yourself how
> >> this works by using the Macro Stepper.
> >>
> >>> (3) finally, what is the recommended way to write this procedure in terms
> >>> of
> >>> performance?
> >>
> >> I took your program, and made all the functions run on much longer
> >> lists. Here are the timings:
> >>
> >> $ r /tmp/even-list.rkt
> >> 'plain
> >> cpu time: 1288 real time: 1294 gc time: 936
> >> 't
> >> cpu time: 440 real time: 441 gc time: 320
> >> 'for/fold
> >> cpu time: 484 real time: 485 gc time: 328
> >> 'mcons
> >> cpu time: 204 real time: 204 gc time: 148
> >> 'mcons-convert
> >> cpu time: 632 real time: 631 gc time: 416
> >> 'for/list
> >> cpu time: 460 real time: 460 gc time: 332
> >>
> >> 'mcons-convert is one that uses `mcons`, but converts back to plain
> >> `cons` at the end.
> >>
> >> Sam
> >> ____________________
> >> Racket Users list:
> >> http://lists.racket-lang.org/users
> >
> ____________________
> Racket Users list:
> http://lists.racket-lang.org/users
____________________
Racket Users list:
http://lists.racket-lang.org/users
