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 ____________________ Racket Users list: http://lists.racket-lang.org/users
