Date: Tue, 9 Mar 2004 02:05:02 +0200 (EET) From: Narvi <narvi@haldjas.folklore.ee> To: Colin Percival <colin.percival@wadham.ox.ac.uk> Cc: freebsd-chat@freebsd.org Subject: Re: FreeBSD Most wanted Message-ID: <20040307213212.N68396@haldjas.folklore.ee> In-Reply-To: <6.0.1.1.1.20040307184942.08d74718@imap.sfu.ca> References: <Pine.LNX.4.43.0403011839470.3269-100000@pilchuck.reedmedia.net> <20040306005744.T38020@haldjas.folklore.ee> <20040306013914.D38020@haldjas.folklore.ee> <6.0.1.1.1.20040306214526.08c5ed70@imap.sfu.ca> <20040306141742.4f41ba27.cpressey@catseye.mine.nu> <20040307202336.K68396@haldjas.folklore.ee> <6.0.1.1.1.20040307184942.08d74718@imap.sfu.ca>
next in thread | previous in thread | raw e-mail | index | archive | help
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 > >
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040307213212.N68396>