hello,
i have some data which is currently stored in a array/vector for fast
access ( i scan over the elements).
i would prefer to have a list instead, but i do need to access elements of
the list sequentially,
sometimes from left to right (next element) and sometimes right to left
(previous element).
accessing the list via nth is said to be no good, because it is not very
efficient.
how is it done more efficient?
regards
kp
From: David Bakhash
Subject: Re: howto: previous/next element of a list
Date:
Message-ID: <cxjpv272seh.fsf@acs5.bu.edu>
The reason people use lists so often is actually a mystery to me. There are
lots of times in Lisp programs where lists are used when arrays should be, and
programs would be faster.
On the other hand, lists make life easy. insertion, changing length,
deletion, etc. are all very easy and efficient with lists. Also, lists can be
coaxed into being stacks and queues. They're an all-around good data
structure to have.
For what you describe, i.e. having a next/previous operator, I think arrays
should be fine (unless you left something out). arrays simply have bounds
[0,(1- length)], so the next/previous ops are easy as long as you keep track
of the current index. So there you go. If you need it to grow, use:
:adjustable t
when you make the array.
Oh. and if insertion is rare, but it happens, then you can acheive it like
this:
given: vector V of length n
Want to insert object X in position k < n of vector V:
(setq V (concatenate 'vector
(subseq (the vector V) 0 k)
(vector X)
(subseq (the vector V) k)))
dave
David Bakhash <·····@bu.edu> writes:
> The reason people use lists so often is actually a mystery to me.
Partly tradition, since Lisp did not always have other data structures.
Partly convenience, since lists compose better than arrays, especially
with respect to their printed representation.
Partly storage, since lists take less storage than arrays in many
implementations for very small numbers of elements. (There's a
cross-over, but many lists are short.) Arrays have to store array
element type, number of elements, etc.
Partly access time. Arrays can be very efficient if you are accessing
a number of elements and the compiler knows it, but if you're a function
that has to just find the car of a list or the first element of an array,
it's probably faster to do the former because the latter involves figuring
out the type of the array before you can act while the former can be
dead-reckoned.
Partly that they allow one to work recursively more easily. In T
(a dialect of Scheme), we made operators char and chdr for moving
down strings passing only a single variable, but in most situations,
moving through an array takes two variables, not one. Note that in
some assembly language and in C, motion through some arrays is only
one variable becuase you get a pointer and then you increment the pointer,
but you're working very close to the edge of errors when you do. Lists
are very much safer.
> There are lots of times in Lisp programs where lists are used when
> arrays should be, and programs would be faster.
I bet you're wrong in more cases than you think. And I bet in a lot
more cases than you think, the fact of the speed doesn't matter.
Speed does matter when you are in a critical loop and when your application
actually makes it to deployment. Speed doesn't matter much if you're
not in a time-critical situation and often doesn't matter even if it is
if you're just toying around. People spend too much of their lives
optimizing cases that don't matter, and worrying about faster is not
always right. Being faster to get home for dinner or faster to tell that
a certain idea is not going to work or faster to get a demo togetehr for
funding is often a lot more important than faster to access something that
is going to be constant time or near-constant-time either way and that
differs only in numbers we used to call milliseconds when I started
computer science (that is, instruction times) and that are now receding
well below microseconds with faster processors.
> On the other hand, lists make life easy. insertion, changing length,
> deletion, etc. are all very easy and efficient with lists. Also, lists can be
> coaxed into being stacks and queues. They're an all-around good data
> structure to have.
(I mostly agree with this. To the degree that I disagree, it's mostly
withthe placement of this info in a subordinate position. If you
struck the "on the other hand" part, I'd probably not have quibbled.)
> > For what you describe, i.e. having a next/previous operator, I think arrays
> should be fine (unless you left something out). [...]
If sharing is not involved, you might also consider a structure like:
(defstruct doubly-linked-list
next
prev
data)
Such a list can be easily attached to in both directions and can be moved
back and forward in easily, but is a pain if you have to have shared
subtails since it really just doesn't have any meaning--in this kind of
thing, there really is only one next and one previous--sharing implies
multiple previous. (of course, arrays don't accomodate sharing
very well either. but that's mostly becuase it's the real world, not
the choice of data structure, that is the source of constraint.)