On Thu, 2007-01-18 at 22:59 -0700, Robert Dodier wrote:
. . .
> Well, time to access an element is constant (I hope) but time
> to access a list element depends on the position of the element --
> it takes longer to get to the elements at the end of the list.
> The time to get the n-th element might be logarithmic or linear
> or something else, but for various Lisp implementations that I've
> looked at, it's not constant. I'm not sure at this point if constant-
> time access for lists is worth the trouble, but I also don't want to
> rule it out.
But, but, isn't that why lisp has arrays? When you want random access
with constant access time and static size, use an array; when you want
sequential access and dynamic size, use a (usually singly-linked) list.
Think of the number of times an array is used in a loop with an index
blithely marching up from 0 -- why not cdr down a list instead. The
language provides two different data structures with different
characteristics; the programmer's job is to make the right choice.
I'm using Python a little now, and its decision to call arrays lists
drives me nuts. List operations are provided with unknown and unreliable
performance characteristics. Part of the problem with Python's "list"
type is that dynamic operations are provided, but the representation is
a C array; as a result when dynamic operations are used copying with
resizing occurs under the hood, at great cost. To my mind that makes
Python a bad choice for any application where predictable performance
matters at all (not just performance critical tasks).
-- Bill Wood