At Sat, 08 Mar 2014 12:33:42 -0500, "David T. Pierson" wrote:
> Also, when I do:
>
> $ racket
> Welcome to Racket v6.0.0.2.
> > (let ((ls (make-list 50000000 0)))
> (time (list? ls))
>
> (time (list? ls))
>
> (time (list? ls))
>
> (time (list? ls))
>
> (time (list? ls)))
>
> cpu time: 220 real time: 220 gc time: 0
> cpu time: 112 real time: 112 gc time: 0
> cpu time: 60 real time: 58 gc time: 0
> cpu time: 28 real time: 29 gc time: 0
> cpu time: 16 real time: 15 gc time: 0
> #t
>
> Why does the time decrease gradually, rather than the 2nd and subsequent
> times being roughly equivalent?
When `list?` explores N pairs to determine whether its argument is a
list, it sets a bit once after N/2 pairs. That choice avoids the cost
of setting bits everywhere while providing amortized constant time for
`rest` in something like
(define (len l)
(if (empty? l)
0
(add1 (len (rest l)))))
Setting the bit at N/2 pairs also happens to reuse references that are
already in flight for tortoise--hare cycle detection. (Whether it's
worth having immutable cyclic pairs is yet another question, though.)
____________________
Racket Users list:
http://lists.racket-lang.org/users
