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

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

> 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