FreeBSD Most wanted

[Narvi]

On Sun, 7 Mar 2004, Colin Percival wrote:

> At 18:42 07/03/2004, Narvi wrote:
> >On Sat, 6 Mar 2004, Colin Percival wrote:
> > >    Perhaps not, but it's much easier to implement an unsorted list. :-)
>  > ...
> >If you know the max number of elements, use an array of pointers + counter
> >instead of list. scanning an array is much nicer than scanning a list
>
>    Sorry, bad choice of words on my part.  When I said "unsorted list", I
> meant "array".  (That's what I get for skipping an undergraduate CS degree
> and going straight to the doctorate...)
>

I guess i should consistently say 'linked list' when I mean that.

> >I think the problem is that [most undergraduate programs] don't have a
> >course on how to select data structures at all AFAICT.
>
>    Many do, but they are usually taught entirely from the point of view
> of asymptotics.
>
> "Hash tables operate in O(1) time!"
> (Or somewhere around O(log(n)) if they're being unusually honest.)
>
> "Scanning an array takes O(n) time!"
>

Heh. Well, I guess its important that people know about asymptotic
complexity. But that doesn't really help them all that much when picking a
data structre for an application where you need to juggle a lot of extra
parameters like:

	* memory hierarchy
	* online vs offline
	* in-core vs out-of-core
	* memory over head per item
	* overhead in case of more than one thread


> Obviously hash tables are better than arrays for all n > 1, right?
>
> Colin Percival
>
>