FreeBSD Most wanted

[Colin Percival]

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 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!"

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

Colin Percival