From: Greg
Subject: Tradeoffs between dotted pair and regular cons
Date:
Message-ID: <m3679c171t.fsf@erols.com>
Please forgive my possibly incorrect terminology...
In Common Lisp, what are the tradeoffs between the 2 following
structures with respect to storage space, access overhead (car, cdr
or rplac? operations), or other significant properties which I'm
not aware?
( a . b ) or ( a b )
In both cases, a and b are plain old characters
Thanks for your time!
Gregm
In article <··············@erols.com>, Greg <······@erols.com> wrote:
>structures with respect to storage space, access overhead (car, cdr
>or rplac? operations), or other significant properties which I'm
>not aware?
>
>( a . b ) or ( a b )
>
>In both cases, a and b are plain old characters
(a . b) is a single cons. Its car refers to A, its cdr refers to B. Both
components should have similar access overhead.
(a b) is short for (a . (b . nil)). This is two conses. The car of the
first cons refers to A, its cdr refers to the second cons. The car of the
second cons refers to B, its cdr refers to NIL (the empty list). Accessing
the first element of the list will generally be faster than accessing the
second element, since the latter requires an extra indirection through the
second cons. The 2-element list usually takes up twice as much storage as
the cons.
Note that systems with cdr-coding can often implement a 2-element list
using approximately the same storage layout as the cons. But there aren't
many such systems these days (efficient cdr-coding generally requires
special hardware support, so it was mainly done only on Lisp Machines).
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Don't bother cc'ing followups to me.