From owner-freebsd-chat@FreeBSD.ORG Sun Mar 7 10:59:18 2004 Return-Path: Delivered-To: freebsd-chat@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id C128816A4CE for ; Sun, 7 Mar 2004 10:59:18 -0800 (PST) Received: from tx3.oucs.ox.ac.uk (tx3.oucs.ox.ac.uk [163.1.2.167]) by mx1.FreeBSD.org (Postfix) with ESMTP id 2C41043D1D for ; Sun, 7 Mar 2004 10:59:18 -0800 (PST) (envelope-from colin.percival@wadham.ox.ac.uk) Received: from scan3.oucs.ox.ac.uk ([163.1.2.166] helo=localhost) by tx3.oucs.ox.ac.uk with esmtp (Exim 4.24) id 1B03Ub-0008SL-NP for freebsd-chat@freebsd.org; Sun, 07 Mar 2004 18:59:17 +0000 Received: from rx3.oucs.ox.ac.uk ([163.1.2.165]) by localhost (scan3.oucs.ox.ac.uk [163.1.2.166]) (amavisd-new, port 25) with ESMTP id 32126-09 for ; Sun, 7 Mar 2004 18:59:17 +0000 (GMT) Received: from gateway.wadham.ox.ac.uk ([163.1.161.253]) by rx3.oucs.ox.ac.uk with smtp (Exim 4.24) id 1B03Ub-0008SE-A0 for freebsd-chat@freebsd.org; Sun, 07 Mar 2004 18:59:17 +0000 Received: (qmail 8714 invoked by uid 1004); 7 Mar 2004 18:59:16 -0000 Received: from colin.percival@wadham.ox.ac.uk by gateway by uid 71 with qmail-scanner-1.20 (clamscan: 0.67. sweep: 2.18/3.79. Clear:RC:1(163.1.161.131):. Processed in 0.073537 secs); 07 Mar 2004 18:59:16 -0000 Received: from dhcp1131.wadham.ox.ac.uk (HELO piii600.wadham.ox.ac.uk) (163.1.161.131) by gateway.wadham.ox.ac.uk with SMTP; 7 Mar 2004 18:59:16 -0000 Message-Id: <6.0.1.1.1.20040307184942.08d74718@imap.sfu.ca> X-Sender: cperciva@imap.sfu.ca (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 6.0.1.1 Date: Sun, 07 Mar 2004 18:59:14 +0000 To: Narvi From: Colin Percival In-Reply-To: <20040307202336.K68396@haldjas.folklore.ee> References: <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> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed cc: freebsd-chat@freebsd.org Subject: Re: FreeBSD Most wanted X-BeenThere: freebsd-chat@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Non technical items related to the community List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 07 Mar 2004 18:59:18 -0000 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