Newbie question again.. when I take the length of a list, e.g.: (length '(a
b c d e)), does it go through the entire list and count the number of
elements, thus running in linear time or does lisp keep track of the length
for you and simply look it up, taking constant time? Thanks
"Fringe" <·········@fdaddsfdsa-HotMail-dfsad.com> writes:
> Newbie question again.. when I take the length of a list, e.g.:
> (length '(a b c d e)), does it go through the entire list and count
> the number of elements, thus running in linear time or does lisp
> keep track of the length for you and simply look it up, taking
> constant time?
Taking the length of a list is O(N); there's no other way than to go
through the entire list. On the other hand, taking the length of a
vector is O(1). You can of course make your own data-structure that
holds a list and remembers the lenght of this list.
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld <······@cs.uit.no> writes:
> "Fringe" <·········@fdaddsfdsa-HotMail-dfsad.com> writes:
>
>> Newbie question again.. when I take the length of a list, e.g.:
>> (length '(a b c d e)), does it go through the entire list and count
>> the number of elements, thus running in linear time or does lisp
>> keep track of the length for you and simply look it up, taking
>> constant time?
>
> Taking the length of a list is O(N); there's no other way than to go
> through the entire list. On the other hand, taking the length of a
> vector is O(1). You can of course make your own data-structure that
> holds a list and remembers the lenght of this list.
Just a brief additional note: a Lisp list is just an assembly of
conses. None of the participating conses "knows" that it is part of
a list. The reference to a list is in fact just a reference to a
cons cell. It "becomes" a reference to a list only through the
treatment the programmer gives it (e.g. by applying LENGTH to it).
---Vassil.
--
Vassil Nikolov <········@poboxes.com>
Hollerith's Law of Docstrings: Everything can be summarized in 72 bytes.
Frode Vatvedt Fjeld <······@cs.uit.no> writes:
> "Fringe" <·········@fdaddsfdsa-HotMail-dfsad.com> writes:
>
> > Newbie question again.. when I take the length of a list, e.g.:
> > (length '(a b c d e)), does it go through the entire list and count
> > the number of elements, thus running in linear time or does lisp
> > keep track of the length for you and simply look it up, taking
> > constant time?
>
> Taking the length of a list is O(N); there's no other way than to go
> through the entire list. On the other hand, taking the length of a
> vector is O(1). You can of course make your own data-structure that
> holds a list and remembers the lenght of this list.
Which is quite difficult because of nconc, (setf cdr), etc. But for
some of your lists, you could do it.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.
The complexity of length is always the length of the list.
There is no caching of the length.
Anyway, caching the length would not work, since cons cells are mutable, so
that
modifying some cell could not be notified to all the cells pointing directly
or indirectly to the modified one.
Probably you should try to use vectors instead of lists to implement your
sequence.
TH
"Fringe" <·········@fdaddsfdsa-HotMail-dfsad.com> a �crit dans le message de
·························@newssvr27.news.prodigy.com...
> Newbie question again.. when I take the length of a list, e.g.: (length
'(a
> b c d e)), does it go through the entire list and count the number of
> elements, thus running in linear time or does lisp keep track of the
length
> for you and simply look it up, taking constant time? Thanks
>
>