From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id EAA25166; Sun, 4 May 2003 04:08:51 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id EAA24660 for ; Sun, 4 May 2003 04:08:49 +0200 (MET DST) Received: from ajax.cs.uga.edu (ajax.cs.uga.edu [128.192.251.3]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h4428mT01950 for ; Sun, 4 May 2003 04:08:48 +0200 (MET DST) Received: from cs.uga.edu (ajax.cs.uga.edu [128.192.251.3]) by ajax.cs.uga.edu (8.9.3/8.9.3) with ESMTP id WAA02808; Sat, 3 May 2003 22:08:44 -0400 (EDT) To: "Mattias Waldau" Cc: "'Ocaml Mailing List'" From: cashin@cs.uga.edu Subject: Re: [Caml-list] Efficiency of 'a list Date: Sat, 03 May 2003 22:08:45 -0400 In-Reply-To: <03ea01c311a3$ee573560$0200a8c0@gateway> ("Mattias Waldau"'s message of "Sat, 3 May 2003 20:43:41 +0200") Message-ID: <87r87fv4ya.fsf@cs.uga.edu> User-Agent: Gnus/5.090014 (Oort Gnus v0.14) Emacs/21.2 (i386-debian-linux-gnu) References: <03ea01c311a3$ee573560$0200a8c0@gateway> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Spam: no; 0.00; caml-list:01 mattias:01 waldau:01 hash:01 kernel:01 ocaml:01 writes:01 pgp:02 tree:02 silly:02 suppose:03 data:03 array:04 efficiency:05 efficient:05 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk "Mattias Waldau" writes: > *** Do not use lists, there is always a better datastructure *** That's kind of silly. Sometimes lists are the natural datastructure to use. If you know what you're doing, use lists when appropriate! I suppose the reason nobody else has responded to this over-generalization is that it's really not specific to ocaml and so of questionable relevance here. However, I don't like thinking that people who aren't yet comfortable with data structures may be reading this suggestion and taking it literally. Whenever you've got a situation where access is always via straightforward iteration and modification is at the beginning or end of a sequence, it doesn't make sense to use a hash table or even a tree. When you don't know the size ahead of time, it doesn't make sense to use an array either. A list is just the right thing in that case. Witness the linux kernel, which uses lists when lists are the most natrural, efficient data structure for the task at hand. ... > The result of this is that you get all these questions in this forum > complaining about performance. Most of the questions would never > have been asked if the author would have used the correct > datastructure, mostly Hash/Map or Set. The solution is not to compound the confusion by saying, "don't use lists". It would be more helpful to point to resources that describe what data structures to use under different circumstances. -- --Ed L Cashin PGP public key: http://noserose.net/e/pgp/ ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners