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 HAA27864; Sun, 4 May 2003 07:32:42 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id HAA27806 for ; Sun, 4 May 2003 07:32:41 +0200 (MET DST) Received: from ajax.cs.uga.edu (ajax.cs.uga.edu [128.192.251.3]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h445WdH03980 for ; Sun, 4 May 2003 07:32:40 +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 BAA06799; Sun, 4 May 2003 01:32:36 -0400 (EDT) To: alc@PublicPropertySoftware.com Cc: "caml Mailing List'" Subject: Re: [Caml-list] Efficiency of 'a list References: <03ea01c311a3$ee573560$0200a8c0@gateway> <87r87fv4ya.fsf@cs.uga.edu> <3EB4922A.A69C2038@PublicPropertySoftware.com> From: Ed L Cashin Date: Sun, 04 May 2003 01:32:37 -0400 Message-ID: <87bryjuvii.fsf@cs.uga.edu> User-Agent: Gnus/5.090014 (Oort Gnus v0.14) Emacs/21.2 (i386-debian-linux-gnu) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Spam: no; 0.00; caml-list:01 hash:01 recursively:01 guesses:01 ocaml:01 writes:01 pgp:02 tree:02 wrote:03 array:04 efficiency:05 maybe:06 lists:91 looping:08 modification:08 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk alc@PublicPropertySoftware.com writes: > cashin@cs.uga.edu wrote: >> >> 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. > > I've done a little timing of things, and according to my results: > If you care about efficiency and use OCaml, you should use lists > fairly often, ie if you are always looping and accessing the elements > in order. OCaml can iterate through a list (recursively) about twice as > fast as it can iterate through an array. It can iterate through a > list about as fast as or maybe even a little faster than C or C++ can > iterate through an array. Huh. I wonder why. I had a couple of guesses, but I don't know my way around the ocaml sources, so I couldn't follow up on them (without spending a bit more time than I have ;). -- --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