This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] function
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Issac Trotts Subject: Re: [Caml-list] function
```
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

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

```