Re: [Caml-list] function

[Issac Trotts <ijtrotts@ucdavis.edu>]

Oleg wrote:
> On Thursday 05 December 2002 03:24 pm, Issac Trotts wrote:
> >   List.concat (List.map to_list2 strs);;
> 
>     ^^^^^^^^^
> 
> > > 2)  What is the complexity of your function f ?
> >
> > The new ones have linear time complexity w.r.t. the number of
> > characters.  The old one has quadratic time complexity.
> 
> Issac
> 
> I haven't analyzed your whole functions, but List.flatten'ing alone is 
> O(S*L^2), so while it may be linear WRT the number of characters in one 
> string, it's not necessarily linear WRT the total number of characters. See 
> my version of f for O(L*S) time.
> 
> Cheers
> Oleg

Thanks for pointing this out.

Here's flatten, from list.ml:

  let rec flatten = function
      [] -> []
    | l::r -> l @ flatten r

  let concat = flatten

Here's (@), from pervasives.ml : 

  let rec (@) l1 l2 =
    match l1 with
      [] -> l2
    | hd :: tl -> hd :: (tl @ l2)

If the given list has L elements, each with S items, then flatten should 
O((L*S)*L) = O(S*L^2) time, since you have to keep on churning through
every single element in the ever-expanding l at every recursive flatten 
call.  That's too bad.

Here's an experiment I tried:

$ cat ftime.ml 

  let rec make_list_of_lists = function 
    | 0 -> []
    | n -> [1;2;3;4;5;6;7;8] :: make_list_of_lists(n-1)

  let _ = 
    let n = int_of_string(Sys.argv.(1)) in
    let lol = make_list_of_lists n in
    ignore(List.flatten(lol))
  ;;

$ ocamlopt -o ftime ftime.ml
$ for (( i=0; $i<100; i++ )) 
  do 
    /usr/bin/time -o data -a -f "%U" ./ftime "$i"000  
  done 
$ gnuplot
  > plot 'data'

I guess it looks linear because of the small input size.
This gives me the impression that List.flatten is practical,
at least for small data sets.

Issac


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