From owner-freebsd-chat@FreeBSD.ORG Mon Mar 8 16:05:05 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 B350116A4CE for ; Mon, 8 Mar 2004 16:05:05 -0800 (PST) Received: from haldjas.folklore.ee (Haldjas.folklore.ee [193.40.6.121]) by mx1.FreeBSD.org (Postfix) with ESMTP id 127AD43D1F for ; Mon, 8 Mar 2004 16:05:05 -0800 (PST) (envelope-from narvi@haldjas.folklore.ee) Received: from haldjas.folklore.ee (localhost [127.0.0.1]) by haldjas.folklore.ee (8.12.10/8.12.10) with ESMTP id i29052UA006730; Tue, 9 Mar 2004 02:05:02 +0200 (EET) (envelope-from narvi@haldjas.folklore.ee) Received: from localhost (narvi@localhost)i29052gq006727; Tue, 9 Mar 2004 02:05:02 +0200 (EET) (envelope-from narvi@haldjas.folklore.ee) Date: Tue, 9 Mar 2004 02:05:02 +0200 (EET) From: Narvi To: Colin Percival In-Reply-To: <6.0.1.1.1.20040307184942.08d74718@imap.sfu.ca> Message-ID: <20040307213212.N68396@haldjas.folklore.ee> References: <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> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Spam-Status: No, hits=0.0 required=8.0 tests=none autolearn=no version=2.63 X-Spam-Checker-Version: SpamAssassin 2.63 (2004-01-11) on haldjas.folklore.ee 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: Tue, 09 Mar 2004 00:05:05 -0000 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 > >