FreeBSD Most wanted
colin.percival at wadham.ox.ac.uk
Sun Mar 7 10:59:18 PST 2004
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
"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?
More information about the freebsd-chat