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
>
>
_______________________________________________
freebsd-chat@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-chat
To unsubscribe, send any mail to "freebsd-chat-unsubscribe@freebsd.org"