> > I've been doing some exploring on the net about data structures. EVERY
> > tutorial/explanation/what-have-you tells you what they are, how they work,
> > etc., but they do not under any circumstances tell you what you would use
> > them for...why would I use a stack, or a linked list, or whatever?
Knuth, The Art of Computer Programming, vol II, (from memory)
will pedanticly lead you through sorting theory. The question
of which to use where depends on:
size -- will a linear search work, or is extreme hashing
needed to minimize seeks
growth -- is it a list of 60k zipcodes and relatively
static, or 80M telephone numbers, with 10% changing each year,
and growing at 5% pA
speed -- is encoding needed/useful to control data store
size, or is fast (deterministic<?>) access needed
We might accept a linear search and pushes and pops off a
single stack in ram in writing a single threaded Forth
interpreter on a stand alone machine; The host presenting the
SLUG website has also been handling the 'distrowatch' website
as the prime site and reference rsync mirror recently. This
requires lots of parallel searches into the data store (here
webpages and filesystem) to manage the load acceptably, and
I've been tuneing and watching it pretty carefully.
The course notes at
http://www.cs.columbia.edu/~novik/cs3133/
go into design considerations in the lecture notes to some
degree. A nice speed vs. complexity analysis is at:
http://www.cs.columbia.edu/~novik/cs3133/notes/lect07.html
-- Russ Herrold
This archive was generated by hypermail 2.1.3 : Fri Aug 01 2014 - 19:35:32 EDT