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 WAA12494; Fri, 6 Dec 2002 22:30:52 +0100 (MET)
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 WAA18172 for <caml-list@pauillac.inria.fr>; Fri, 6 Dec 2002 22:30:51 +0100 (MET)
Received: from casablanca.ucdavis.edu (casablanca.ucdavis.edu [169.237.104.164])
	by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id gB6LUo105971
	for <caml-list@inria.fr>; Fri, 6 Dec 2002 22:30:50 +0100 (MET)
Received: from boson.localdomain.fake (postfix@[128.120.141.218])
	by casablanca.ucdavis.edu (8.11.6/8.11.0/virus-scan-4.0.1) with ESMTP id gB6LUl312035
	for <caml-list@inria.fr>; Fri, 6 Dec 2002 13:30:47 -0800 (PST)
Received: by boson.localdomain.fake (Postfix, from userid 1000)
	id 1C474A00C9; Fri,  6 Dec 2002 13:31:21 -0800 (PST)
Date: Fri, 6 Dec 2002 13:31:21 -0800
From: Issac Trotts <ijtrotts@ucdavis.edu>
To: OCaml Mailing List <caml-list@inria.fr>
Subject: Re: [Caml-list] function
Message-ID: <20021206213120.GC696@boson.ucdavis.edu>
References: <20021203232211.GC22545@beech> <200212051000.LAA22469@pauillac.inria.fr> <20021205202448.GB524@boson.ucdavis.edu> <200212051800.55361.oleg_inconnu@myrealbox.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <200212051800.55361.oleg_inconnu@myrealbox.com>
User-Agent: Mutt/1.3.28i
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk


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