At Tue, 15 May 2012 06:31:13 -0500, Robby Findler wrote:
> FWIW, the list? check that is inside first and rest caches its result
> in the header information in the cons cells it traverses.
In other words, `first and `rest' are amortized constant-time, due to
the use of the amortized constant-time `list?'.
You can think of the cost of `list?' as being charged to the list
creation, and each single list creation n your example takes about 10
times as long as the 1000 accesses, so the cost is very small overall.
In particular, if you add a second sum loop on the same list, it takes
the same amount of time for both.
For example, with
#lang racket
(define (test len times)
(let ((ll (time (make-list len 1))))
(time (for/sum ((i (in-range times)))
(+ (first ll)
(second ll))))
(time (for/sum ((i (in-range times)))
(+ (first ll)
(second ll))))))
(test (expt 10 6) 100000)
(test (expt 10 7) 100000)
I get
cpu time: 74 real time: 75 gc time: 63
cpu time: 14 real time: 15 gc time: 0
cpu time: 5 real time: 5 gc time: 0
200000
cpu time: 1429 real time: 1433 gc time: 1342
cpu time: 98 real time: 98 gc time: 0
cpu time: 4 real time: 5 gc time: 0
200000
Some functions, such as `list-ref', do not have a `list?' contract
because they are intended to work on more values than lists --- which
means that some of them, like `list-ref', are at this point misnamed.
> On Tue, May 15, 2012 at 3:06 AM, Pierpaolo Bernardi <olopie...@gmail.com>
> wrote:
> > On Mon, May 14, 2012 at 8:16 PM, Jay McCarthy <jay.mccar...@gmail.com>
> > wrote:
> >> They could be identical, but they are different because one set is
> >> about lists and the other is about pairs. The fact that pairs may be
> >> used to implement lists is immaterial.
> >>
> >> You should really never use the c[ad]*r functions unless you are
> >> specifically dealing with pairs.
> >
> > So, what should one use on proper lists?
> >
> > - c[ad]*r no;
> > - first and rest appear to be O(n):
> >
> > #lang racket
> >
> > (define (test len times)
> > (let ((ll (make-list len 1)))
> > (time (for/sum ((i (in-range times)))
> > (+ (first ll)
> > (second ll))))))
> >
> >> (test (expt 10 6) 1000)
> > cpu time: 15 real time: 16 gc time: 0
> > 2000
> >> (test (expt 10 7) 1000)
> > cpu time: 109 real time: 109 gc time: 0
> > 2000
> >
> > Why this check is made only for first, rest, etc, and not for all the
> > functions that take a list?
> >
> > For example, (list-ref list 1) appears to be O(1) in the length of list.
> >
> > ?
> >
> > P.
____________________
Racket Users list:
http://lists.racket-lang.org/users
