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 LAA21818; Thu, 29 Jul 2004 11:13:03 +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 LAA21894 for ; Thu, 29 Jul 2004 11:13:02 +0200 (MET DST) Received: from ppsw-3.csi.cam.ac.uk (ppsw-3.csi.cam.ac.uk [131.111.8.133]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i6T9CxEV030601 for ; Thu, 29 Jul 2004 11:13:01 +0200 Received: from athena.jesus.cam.ac.uk ([131.111.243.130]:2102 helo=pooh) by ppsw-3.csi.cam.ac.uk (smtp.hermes.cam.ac.uk [131.111.8.153]:465) with esmtp (SSLv3:RC4-MD5:128) (Exim 4.34) id 1Bq6y6-0004E8-AW for caml-list@inria.fr; Thu, 29 Jul 2004 10:12:54 +0100 From: Daniel Andor To: Ocaml Subject: Re: [Caml-list] looping recursion Date: Thu, 29 Jul 2004 10:13:12 +0100 User-Agent: KMail/1.6.2 References: <16646.64470.304530.264731@soggy.deldotd.com> <200407282040.40600.jon@jdh30.plus.com> In-Reply-To: MIME-Version: 1.0 Content-Disposition: inline Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Message-Id: <200407291013.12467.da209@cam.ac.uk> X-Cam-ScannerInfo: http://www.cam.ac.uk/cs/email/scanner/ X-Cam-AntiVirus: No virus found X-Cam-SpamDetails: Not scanned X-Miltered: at nez-perce with ID 4108BF9B.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 recursion:01 2004:99 brogoff:01 2004:99 38,:01 brogoff:01 000,:01 damned:01 lemme:01 ocamlc:01 usr:01 vanilla:01 usr:01 ocamlopt:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Wednesday 28 July 2004 10:22 pm, brogoff wrote: > On Wed, 28 Jul 2004, Jon Harrop wrote: > > On Wednesday 28 July 2004 17:38, brogoff wrote: > > > > brogoff wrote: > > > > > Sometimes lists are best. If lists are OK for 100, 1_000, or 10_000 > > > > > items, why not 100_000 or 1_000_000? Map and friends shouldn't blow > > > > > stack. [...] > > What's wrong with List.rev_map, List.rev (List.rev_map ...), increasing > > the size of the VM's stack, using native code or even writing your own, > > tail-recursive map? > > I'm pretty damned well aware that I can reverse a rev mapped list. If you've got the mutable list version of map to hand, and you are happy with that, then that's clearly the way to go. But the rev version of map is the same linear complexity as all the map functions, and is not much more inefficient than the stack version: CPU or memory-wise (given my limited understanding of the GC). So if you were happy with List.map, except that it blew up on you, then you should definitely be happy with List.rev (List.rev_map ..). Lemme try it out (10^6 elements): ocamlc: rev rev_map version: 2 WALL ( 1.19 usr + 0.02 sys = 1.21 CPU) vanilla map: 7 WALL ( 6.50 usr + 0.09 sys = 6.59 CPU) ocamlopt: rev rev_map version: 1 WALL ( 0.81 usr + 0.03 sys = 0.84 CPU) vanilla map: 2 WALL ( 2.45 usr + 0.02 sys = 2.47 CPU) Wow, that was unexpected! > Does it occur to you that that is not efficient? Not any more! Daniel. ------------------- 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