Date: Sun, 07 Mar 2004 18:59:14 +0000 From: Colin Percival <colin.percival@wadham.ox.ac.uk> To: Narvi <narvi@haldjas.folklore.ee> Cc: freebsd-chat@freebsd.org Subject: Re: FreeBSD Most wanted Message-ID: <6.0.1.1.1.20040307184942.08d74718@imap.sfu.ca> In-Reply-To: <20040307202336.K68396@haldjas.folklore.ee> References: <Pine.LNX.4.43.0403011839470.3269-100000@pilchuck.reedmedia.net> <EABDE846-6EF2-11D8-AE09-000A95DA58FE@jimz.net> <20040306005744.T38020@haldjas.folklore.ee> <20040305153505.74061868.cpressey@catseye.mine.nu> <20040306013914.D38020@haldjas.folklore.ee> <404A465A.1040009@stephanmantler.com> <6.0.1.1.1.20040306214526.08c5ed70@imap.sfu.ca> <20040306141742.4f41ba27.cpressey@catseye.mine.nu> <6.0.1.1.1.20040306221435.03a97e20@imap.sfu.ca> <20040307202336.K68396@haldjas.folklore.ee>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?6.0.1.1.1.20040307184942.08d74718>