Just curious. How often do you choose to use a list instead of an
array?
Lists are good only when you always iterate through them, and arrays
are useful when you need to do random access. Even though the
prevalent use of a data structure is iterative, it seems like there is
always at least one place where I need to do random access. So arrays
predominate over lists.
Is this true of you?
--------------------------------------------------
Thaddeus L. Olczyk, PhD
Think twice, code once.
Sounds like a case of prmature optimization:
"Premature optimization is the root of all evil."
Donald Knuth
Thaddeus L Olczyk wrote:
> Just curious. How often do you choose to use a list instead of an
> array?
>
> Lists are good only when you always iterate through them, and arrays
> are useful when you need to do random access. Even though the
> prevalent use of a data structure is iterative, it seems like there is
> always at least one place where I need to do random access. So arrays
> predominate over lists.
>
> Is this true of you?
> --------------------------------------------------
> Thaddeus L. Olczyk, PhD
> Think twice, code once.
Thaddeus L Olczyk <······@interaccess.com> writes:
> Just curious. How often do you choose to use a list instead of an
> array?
>
> Lists are good only when you always iterate through them, and arrays
> are useful when you need to do random access. Even though the
> prevalent use of a data structure is iterative, it seems like there is
> always at least one place where I need to do random access. So arrays
> predominate over lists.
>
> Is this true of you?
Actually, the problem with arrays is that they have overhead that makes
them less worthwhile for small cases.
They are more expensive to extend, harder to share subparts with,
they have to do do bounds checking the cost of which is probably more
than the cost of doing a couple of cdrs, etc.
For long lists, certainly, it's worth thinking about using other data
structures, but for short lists, I recommend you dno't think in terms
of algorithmic complexity because the constant factors that are usually
omitted in Big-O analysis probably dominate.
Just write your code the way it feels reasonable and worry about whether
it's fastest when you go to tune it for production.
I'd bet 99+% of programs that people write never make it to market or
other "deployment" and work perfectly fine for what they are used for.
It's often quite surprising where the REAL bottlenecks are in
production code--it's rarely where you'd think. At least in my
experience. And it's easier to use metering tools to spot them than
to commit your life to programming the hard way just on the off chance
it will turn out to matter.
"Thaddeus L Olczyk" <······@interaccess.com> wrote in message
·······································@4ax.com...
> Just curious. How often do you choose to use a list instead of an
> array?
>
> Lists are good only when you always iterate through them, and arrays
> are useful when you need to do random access. Even though the
> prevalent use of a data structure is iterative, it seems like there is
> always at least one place where I need to do random access. So arrays
> predominate over lists.
Not so for me. If I have a large amount of data to organize I do not
put it into an array and "randomly" search for it. I organize the data
based on its inherent structure (ordering). Then I build a custom data
storage model based on that inherent ordering. Even though I may
have what looks like an array, it has order associated with it. Conses
also have an advantage over arrays and that is that they can be easily
organized to be a tree, which has great utility. Many forms of data
can be organized into trees (maybe even a circualr one).
Since data and programs in Lisp kind of blur lists predominate over
arrays, as programs are not arrays, but lists (trees).
Wade
"Wade Humeniuk" <····@nospam.nowhere> writes:
> "Thaddeus L Olczyk" <······@interaccess.com> wrote in message
> ·······································@4ax.com...
> > Just curious. How often do you choose to use a list instead of an
> > array?
> >
> > Lists are good only when you always iterate through them, and arrays
> > are useful when you need to do random access. Even though the
> > prevalent use of a data structure is iterative, it seems like there is
> > always at least one place where I need to do random access. So arrays
> > predominate over lists.
>
> Not so for me. If I have a large amount of data to organize I do not
> put it into an array and "randomly" search for it. I organize the data
> based on its inherent structure (ordering). Then I build a custom data
> storage model based on that inherent ordering. Even though I may
> have what looks like an array, it has order associated with it. Conses
> also have an advantage over arrays and that is that they can be easily
> organized to be a tree, which has great utility. Many forms of data
> can be organized into trees (maybe even a circualr one).
>
I find lists particularly suitable for simple queues. Its a little
clumsy maintaining the head and tail, but nothing a macro won't
trivially handle.
Gregm
"Wade Humeniuk" <····@nospam.nowhere> writes:
> "Thaddeus L Olczyk" <······@interaccess.com> wrote in message
> ·······································@4ax.com...
> > Just curious. How often do you choose to use a list instead of an
> > array?
> >
> > Lists are good only when you always iterate through them, and arrays
> > are useful when you need to do random access. Even though the
> > prevalent use of a data structure is iterative, it seems like there is
> > always at least one place where I need to do random access. So arrays
> > predominate over lists.
>
> Not so for me. If I have a large amount of data to organize I do not
> put it into an array and "randomly" search for it. I organize the data
> based on its inherent structure (ordering). Then I build a custom data
> storage model based on that inherent ordering. Even though I may
> have what looks like an array, it has order associated with it. Conses
> also have an advantage over arrays and that is that they can be easily
> organized to be a tree, which has great utility. Many forms of data
> can be organized into trees (maybe even a circualr one).
>
> Since data and programs in Lisp kind of blur lists predominate over
> arrays, as programs are not arrays, but lists (trees).
Compiled functions may be implemented in arrays.
In emacs:
(show (symbol-function 'save-buffer))
==> #[(&optional args) "\305 \306 \307V\203
\2036
(show (aref (symbol-function 'save-buffer) 1))
==> "\305 \306 \307V\203
\2036
--
__Pascal_Bourguignon__ http://www.informatimago.com/
----------------------------------------------------------------------
Do not adjust your mind, there is a fault in reality.
Thaddeus L Olczyk wrote:
> Just curious. How often do you choose to use a list instead of an
> array?
Just about always.
> Lists are good only when you always iterate through them, and arrays
> are useful when you need to do random access. Even though the
> prevalent use of a data structure is iterative, it seems like there is
> always at least one place where I need to do random access. So arrays
> predominate over lists.
>
> Is this true of you?
No. I almost never need to do random access. Perhaps you're thinking
of implementations of "tuples," i.e., short data structures of fixed
length (2 to 10 slots), where each slot has a fixed meaning. Then if
you access the 9th slot as often as the first, you could consider that
to be "random" access. Of course, for that kind of data type you would
use 'defstruct', which could be considered as a use of an "array."
If I do need true random access with a subscript computed at run time,
then I do indeed use an array. But even there the construction phase is
often separable from the access phase, and during construction it is
often more convenient to use a list, which gets converted to an array
when it's done. The alternative would be to do some preprocessing to
figure out the size of the array, allocate it, then fill it in. If I've
ever done that in Lisp, it was a long time ago.
Maybe you work in an unusual domain where all the normal rules don't apply.
-- Drew McDermott
Drew McDermott <··················@at.yale.dot.edu> wrote:
+---------------
| If I do need true random access with a subscript computed at run time,
| then I do indeed use an array. But even there the construction phase is
| often separable from the access phase, and during construction it is
| often more convenient to use a list, which gets converted to an array
| when it's done. The alternative would be to do some preprocessing to
| figure out the size of the array, allocate it, then fill it in. If I've
| ever done that in Lisp, it was a long time ago.
+---------------
Well, one of the places the latter style does seem to come naturally is
when loading up an array from a file or stream, where you end up doing
things of this general pattern [which many Lisps handle very efficiently]:
(defun suck-up-file (filename)
(with-open-file (stream filename)
(let* ((length (file-length stream))
(data (make-sequence 'string length))
(length-read (read-sequence data stream)))
(unless (= length-read length)
(error "Incomplete read on ~S: read ~D, should be ~D"
stream length-read length))
data)))
-Rob
p.s. See also CMUCL's READ-N-BYTES...
-----
Rob Warnock, PP-ASEL-IA <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
After a long battle with technology,Thaddeus L Olczyk <······@interaccess.com>, an earthling, wrote:
> Just curious. How often do you choose to use a list instead of an
> array?
>
> Lists are good only when you always iterate through them, and arrays
> are useful when you need to do random access. Even though the
> prevalent use of a data structure is iterative, it seems like there
> is always at least one place where I need to do random access. So
> arrays predominate over lists.
>
> Is this true of you?
No.
- If there's a good likelihood that the number of elements will remain
small, then it is unimportant to allow random access.
- If there is a good likelihood that I'll be walking through all, or
substantially all elements, for a big list, then it is again
unimportant to allow random access.
This precisely parallels the way database accesses will sometimes
revert to sequential scans *even when there might be a relevant
index.*
Lists being a little more convenient to work with, I'd rather throw
data into lists, as "first blush," and revert to smarter data
structures once optimization is no longer premature...
--
(reverse (concatenate 'string "gro.mca" ·@" "enworbbc"))
http://www3.sympatico.ca/cbbrowne/oses.html
"When I was a boy of fourteen, my father was so ignorant I could
hardly stand to have the old man around. But when I got to be
twenty-one, I was astonished at how much the old man had learned in
seven years." -- Mark Twain