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 SAA01066; Thu, 23 Aug 2001 18:11:09 +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 SAA01111 for ; Thu, 23 Aug 2001 18:11:09 +0200 (MET DST) Received: from wsnyc.fame.com (pixnj254.fame.com [192.88.60.254]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id f7NGB7X02084 for ; Thu, 23 Aug 2001 18:11:08 +0200 (MET DST) Received: from CONSULTING2000P (dhcp-ny-245.fame.com [192.88.66.245]) by wsnyc.fame.com (8.9.3/8.9.3) with ESMTP id MAA15806 for ; Thu, 23 Aug 2001 12:11:04 -0400 (EDT) From: "Collin Monahan" To: Subject: [Caml-list] time complexity on basic data types Date: Thu, 23 Aug 2001 12:16:56 -0400 Organization: FAME Information Services, Inc. Message-ID: <000001c12bef$07df7e30$f54258c0@CONSULTING2000P> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_0001_01C12BCD.80CF64D0" X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.2627 Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4522.1200 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk This is a multi-part message in MIME format. ------=_NextPart_000_0001_01C12BCD.80CF64D0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Thanks to everyone who answered my questions yesterday. With respect to arrays and lists, is the complexity for operations on these data structures like "normal?" E.g. random access in arrays in constant time, insertion in lists in constant time, random access in lists in linear time . . . What facilities exist for timing constructs in Caml? I see val times : unit -> process_times in the manual, under unix system calls. If this is like the times() function in Solaris, then it would work. But I think the Caml syntax is messing me up again, because if I type times();; or let foo = times();; into the toplevel, the system indicates that "times" is not bound. Collin Monahan ------=_NextPart_000_0001_01C12BCD.80CF64D0 Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable

Thanks to everyone who answered my questions = yesterday.

With respect to arrays and lists, is the complexity = for operations on these data structures like “normal?” E.g. = random access in arrays in constant time, insertion in lists in constant time, = random access in lists in linear time . . .

What facilities exist for timing constructs in Caml? = I see

= ; val times : unit -> = process_times

in the = manual, under unix system calls. If this is like the times() function in Solaris, then it would work. But I think the Caml syntax is messing = me up again, because if I type

= ; times();;

= ; let foo =3D times();;

into the toplevel, the system indicates that “times” is not = bound.

Collin = Monahan

------=_NextPart_000_0001_01C12BCD.80CF64D0-- ------------------- Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr 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 TAA04390; Thu, 23 Aug 2001 19:23:56 +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 TAA04348 for ; Thu, 23 Aug 2001 19:23:55 +0200 (MET DST) Received: from smtp1.cswv.com (smtp1.cswv.com [4.17.129.17]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id f7NHNrX03083 for ; Thu, 23 Aug 2001 19:23:54 +0200 (MET DST) Received: from smtp1.cswv.com ([4.17.129.17]) by smtp1.cswv.com with Microsoft SMTPSVC(5.5.1877.197.19); Thu, 23 Aug 2001 13:24:59 -0400 Received: FROM exchange1.cswv.com BY smtp1.cswv.com ; Thu Aug 23 13:24:59 2001 -0400 Received: by exchange1.cswv.com with Internet Mail Service (5.5.2653.19) id ; Thu, 23 Aug 2001 13:27:53 -0400 Message-ID: From: "Krishnaswami, Neel" To: caml-list@inria.fr Subject: Re: [Caml-list] time complexity on basic data types Date: Thu, 23 Aug 2001 13:27:45 -0400 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2653.19) Content-Type: text/plain; charset="iso-8859-1" Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Collin Monahan [mailto:cmonahan@fame.com] wrote: > > With respect to arrays and lists, is the complexity for operations > on these data structures like "normal?" E.g. random access in arrays > in constant time, insertion in lists in constant time, random access > in lists in linear time . . . Yep, that's correct. > What facilities exist for timing constructs in Caml? I see > val times : unit -> process_times > in the manual, under unix system calls. If this is like the times() > function in Solaris, then it would work. But I think the Caml syntax > is messing me up again, because if I type > times();; > or > let foo = times();; > into the toplevel, the system indicates that "times" is not bound. Okay, first of all, to reference a name in another module you have to qualify the name with the module. Eg, you'd need to type Unix.times(), rather than just times(). Second, for reasons I don't understand the Unix library is not linked by default, so you need to explicitly specify it when you compile your programs. (This is described at the top of the chapter on the Unix library: ) In addition to this, you can also use the nice profiler that comes with the OCaml distribution, which gives you all sorts of fancy instruction counts. That's in chapter 16 of the Caml manual: -- Neel Krishnaswami neelk@cswcasa.com ------------------- Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr 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 TAA05034; Thu, 23 Aug 2001 19:35:56 +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 TAA05061 for ; Thu, 23 Aug 2001 19:35:55 +0200 (MET DST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f7NHZrH01907; Thu, 23 Aug 2001 19:35:53 +0200 (MET DST) Received: (from xleroy@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id TAA05121; Thu, 23 Aug 2001 19:35:52 +0200 (MET DST) Date: Thu, 23 Aug 2001 19:35:52 +0200 From: Xavier Leroy To: "Krishnaswami, Neel" Cc: caml-list@inria.fr Subject: Re: [Caml-list] time complexity on basic data types Message-ID: <20010823193552.A32344@pauillac.inria.fr> References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 1.0i In-Reply-To: ; from neelk@cswcasa.com on Thu, Aug 23, 2001 at 01:27:45PM -0400 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > > What facilities exist for timing constructs in Caml? I see > > val times : unit -> process_times > > in the manual, under unix system calls. The most portable way to time a piece of code is via the Sys.time() function. It's part of the OCaml standard library, so it's guaranteed to work on all ports of OCaml -- even non-Unix ones. The Unix.times() function is more Unix-specific and is provided by an external library, which you have to request explicitly (as Neel explained). > Second, > for reasons I don't understand the Unix library is not linked by > default, The main reason is that it might not be available (on a non-Unix platform, for instance). (OK, both the Windows and the MacOS ports of OCaml have reasonable Unix emulation built-in, but that wasn't always the case, and hypothetical ports to other OSes might not have it either.) In other terms, the modules that are linked by default, that is, those in the standard library, are the modules that are available everywhere; other modules are in separate libraries, not linked in by default. > In addition to this, you can also use the nice profiler that comes > with the OCaml distribution, which gives you all sorts of fancy > instruction counts. That's in chapter 16 of the Caml manual: > Correct. There's also the option of using ocamlopt -p in conjunction with the Unix profiler "gprof". - Xavier Leroy ------------------- Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr 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 AAA13093; Fri, 24 Aug 2001 00:29:59 +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 AAA13204 for ; Fri, 24 Aug 2001 00:29:58 +0200 (MET DST) Received: from smtprelay3.adelphia.net (smtprelay3.adelphia.net [64.8.25.8]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f7NMTuH08171 for ; Fri, 24 Aug 2001 00:29:56 +0200 (MET DST) Received: from mordor ([24.48.116.108]) by smtprelay3.adelphia.net (Netscape Messaging Server 4.15) with SMTP id GIJL6O00.HAV for ; Thu, 23 Aug 2001 18:30:24 -0400 Message-ID: <002d01c12c23$2179ea40$0200a8c0@buf.adelphia.net> From: "Lars Nilsson" To: References: Subject: Re: [Caml-list] time complexity on basic data types Date: Thu, 23 Aug 2001 18:29:53 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.50.4522.1200 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4522.1200 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk At the risk of making a fool of myself in public, is there such a thing as insertion in a list at all in Ocaml? From what I have seen there is only concatenation of a single element and a list (::), and operations would have to be defined with this by means recursion/iteration. If this is the case, I assume insertion at some point in a list would have O(n) complexity in the general case? If not, what am I missing (@ being something other than I think?) Regards, Lars Nilsson From: "Krishnaswami, Neel" > Collin Monahan [mailto:cmonahan@fame.com] wrote: > > > > With respect to arrays and lists, is the complexity for operations > > on these data structures like "normal?" E.g. random access in arrays > > in constant time, insertion in lists in constant time, random access > > in lists in linear time . . . > > Yep, that's correct. ------------------- Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr 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 CAA15287; Fri, 24 Aug 2001 02:26:41 +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 CAA15070 for ; Fri, 24 Aug 2001 02:26:40 +0200 (MET DST) Received: from moutvdom00.kundenserver.de (moutvdom00.kundenserver.de [195.20.224.149]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f7O0QdH09619 for ; Fri, 24 Aug 2001 02:26:39 +0200 (MET DST) Received: from [195.20.224.209] (helo=mrvdom02.schlund.de) by moutvdom00.kundenserver.de with esmtp (Exim 2.12 #2) id 15a4o2-0004Mw-00; Fri, 24 Aug 2001 02:26:38 +0200 Received: from drms-3e364b94.pool.mediaways.net ([62.54.75.148] helo=ice.gerd-stolpmann.de) by mrvdom02.schlund.de with esmtp (Exim 2.12 #2) id 15a4o2-00073J-00; Fri, 24 Aug 2001 02:26:38 +0200 Received: from localhost (localhost [[UNIX: localhost]]) by ice.gerd-stolpmann.de (8.9.3/8.9.3) id BAA14549; Fri, 24 Aug 2001 01:52:28 +0200 From: Gerd Stolpmann Reply-To: gerd@gerd-stolpmann.de Organization: privat To: "Lars Nilsson" , Subject: Re: [Caml-list] time complexity on basic data types Date: Fri, 24 Aug 2001 01:50:49 +0200 X-Mailer: KMail [version 1.0.28] Content-Type: text/plain References: <002d01c12c23$2179ea40$0200a8c0@buf.adelphia.net> In-Reply-To: <002d01c12c23$2179ea40$0200a8c0@buf.adelphia.net> MIME-Version: 1.0 Message-Id: <01082401522806.02716@ice> Content-Transfer-Encoding: 8bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Fri, 24 Aug 2001, Lars Nilsson wrote: >At the risk of making a fool of myself in public, is there such a thing as >insertion in a list at all in Ocaml? From what I have seen there is only >concatenation of a single element and a list (::), and operations would have >to be defined with this by means recursion/iteration. If this is the case, I >assume insertion at some point in a list would have O(n) complexity in the >general case? If not, what am I missing (@ being something other than I >think?) You are right, only :: is possible. So insertion at arbitrary positions is O(n) time. Gerd -- ---------------------------------------------------------------------------- Gerd Stolpmann Telefon: +49 6151 997705 (privat) Viktoriastr. 45 64293 Darmstadt EMail: gerd@gerd-stolpmann.de Germany ---------------------------------------------------------------------------- ------------------- Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr 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 OAA31718; Fri, 24 Aug 2001 14:28:09 +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 OAA31678 for ; Fri, 24 Aug 2001 14:28:08 +0200 (MET DST) Received: from lri.lri.fr (lri.lri.fr [129.175.15.1]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id f7OCS7n21632 for ; Fri, 24 Aug 2001 14:28:07 +0200 (MET DST) Received: from (filliatr@localhost) by lri.lri.fr (8.11.1/jtpda-5.3.2) id f7OCRnV01855 ; Fri, 24 Aug 2001 14:27:49 +0200 (MEST) From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15238.18501.528683.170652@lri> Date: Fri, 24 Aug 2001 14:27:49 +0200 (MEST) To: "Lars Nilsson" Cc: Subject: Re: [Caml-list] time complexity on basic data types In-Reply-To: <002d01c12c23$2179ea40$0200a8c0@buf.adelphia.net> References: <002d01c12c23$2179ea40$0200a8c0@buf.adelphia.net> X-Mailer: VM 6.49 under Emacs 20.7.1 Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Lars Nilsson writes: > At the risk of making a fool of myself in public, is there such a thing as > insertion in a list at all in Ocaml? From what I have seen there is only > concatenation of a single element and a list (::), and operations would have > to be defined with this by means recursion/iteration. If this is the case, I > assume insertion at some point in a list would have O(n) complexity in the > general case? If not, what am I missing (@ being something other than I > think?) You're right. But a list is not the adequate data structure if you want to insert at some arbitrary points in it. It is a stack-like data structure (i.e. push and pop are O(1)) or can be used when you want to aggregate elements regardless the order and then iterate over / traverse all of them. If you really want to insert at any point in O(1), you may consider using mutable linked lists (see for instance the implementation of the module Queue in ocaml standard library). You loose persistence, but it may not be mandatory in your case. Hope this helps, -- Jean-Christophe Filliatre mailto:Jean-Christophe.Filliatre@lri.fr http://www.lri.fr/~filliatr ------------------- Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr