[Caml-list] time complexity on basic data types

[Caml-list] time complexity on basic data types

[Collin Monahan]

[-- Attachment #1: Type: text/plain, Size: 726 bytes --]

 
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
 

[-- Attachment #2: Type: text/html, Size: 6288 bytes --]

Re: [Caml-list] time complexity on basic data types

[Jean-Christophe Filliatre]

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

Re: [Caml-list] time complexity on basic data types

[Gerd Stolpmann]

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

Re: [Caml-list] time complexity on basic data types

[Lars Nilsson]

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" <neelk@cswcasa.com>
> 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

Re: [Caml-list] time complexity on basic data types

[Xavier Leroy]

> > 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:
> <URI:http://caml.inria.fr/ocaml/htmlman/manual029.html>

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

Re: [Caml-list] time complexity on basic data types

[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.

> 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: <URI:http://caml.inria.fr/ocaml/htmlman/manual065.html>)
 
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:
<URI:http://caml.inria.fr/ocaml/htmlman/manual029.html>

--
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