Re: why are there [v e c t o r s] in Lisp?

[Emanuel Berg]

Barry Margolin <barmar@alum.mit.edu> writes:

> Lists and vectors have different performance
> characteristics. With lists, it's easy to insert and
> delete elements anywhere in the sequence, you just
> add another cons in the cdr chain, but accessing the
> nth element is O(n). With vectors, inserting and
> deleting is expensive, because you have to shift all
> the following elements over to make room (and
> appending may require moving the whole thing,
> because you didn't allocate enough room in the
> original location), but accessing the nth element
> can be done in constant time.
>
> So lists are good for flexible data structures that
> you typically access linearly, while vectors are
> good for random-access data. Also, because vectors
> are stored in contiguous memory, they generally
> exhibit better locality -- this was more important
> in the days when RAM was expensive and limited,
> because paging was more likely when you had a large
> working set.

Right, the international press is happy with
this answer.

-- 
underground experts united
http://user.it.uu.se/~embe8573