[racket] first vs car ; last vs cdr ; empty? vs null?

You want cons (the frequent action) to take constant time: allocate pointer, set two fields. 


On Mar 8, 2014, at 12:33 PM, David T. Pierson wrote:

> On Fri, Mar 07, 2014 at 11:03:57PM -0500, Carl Eastlund wrote:
>> The first/rest operations do not use a memoization table.  They test using
>> the list? primitive, which is built in and actually has a couple of tag
>> bits reserved on every cons object for memoizing its results.  So the
>> operation really is quite fast.
> 
> I take this to mean there is a bit in the cons object for storing
> whether it is a list, and that this bit is set via `list?'.
> 
> Why wouldn't the bit be set via `cons'?
> 
> 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?
> 
> Thanks.
> 
> David
> ____________________
>  Racket Users list:
>  http://lists.racket-lang.org/users