Re: "ocaml_beginners":: Working with arrays and lists
- Karl Zilles wrote:
>You have to copy all these string fragments.
> Martin Jambon wrote:
> > List.fold_right ( ^ ) l "" is not reasonable since it runs in O(n^2).
> Where do you get n^2?
> Looks like O(n) to me, with a high constant due to allocating a new
> string on every concatination.
To concatenate a list of N strings of length M, List.fold_right ( ^ )
copies a total of
2M + 3M + ... + NM = O(N^2 M)
For n = NM, that's O(n^2) : consider the case where all fragments
are small so that M is bounded.
It's O(n) if there are only a few fragments (N bounded)
but clearly the constant is bigger than it should be,
for N > 2 at least.
- On Thu, Aug 05, 2004 at 01:02:52PM +0200, Guido Kollerie wrote:
> Many operations on list can be expressed succinctly by usingString.concat is the way to go in this case as others already
> List.fold_left or List.fold_right:
> let a = [ "qwe" ; "asd" ; "zxc" ];;
> let comma_concat l r =
> match l with
> | "" -> r
> | _ -> if r = "" then l else l ^ ", " ^ r;;
> List.fold_left comma_concat "" a;;
> Yes, comma_concat is kind of ugly but it's List_fold_left that I
> wanted to demonstrate.
wrote, though should you want to program it yourself in a
functional style than this one improves upon what I wrote
let a = [ "qwe" ; "asd" ; "zxc" ];;
let f a = List.fold_left (fun l r -> l ^ ", " ^ r) (List.hd a) (List.tl a);;
[Non-text portions of this message have been removed]