- I'm working through some of the exercises available in the O'Reily

book that is available online at <http://caml.inria.fr/oreily-book/>.

Here is what I came up with for a function that merges two lists. But

I wonder if it is the best solution. It seems like the (accum @

[element]) operations would be O(n) and so the whole function O(n^2).

Or is the @ operator O(1)?

Also, I'm doing a match on (a, b) -- is creating a tuple just for

pattern matching inefficient? Or is ocaml smart enough to not

actually allocate memory for the tuple?

Are there any alternative ways this function could be written short of

replacing the pattern matches with a bunch of if/then expressions?

(* write a function merge_i which takes as input two integer lists sorted

in increasing order and returns a new sorted list containing the

elements of the first two. *)

let merge_i a b =

let rec merge a b accum = match (a, b) with

([], []) -> accum

| ([], head::tail) -> merge [] tail (accum @ [head])

| (head::tail, []) -> merge [] tail (accum @ [head])

| (ahead::atail, bhead::btail) ->

if ahead < bhead then

merge atail b (accum @ [ahead])

else

merge a btail (accum @ [bhead])

in

merge a b []

;;

--

Don't send mail to Duke.Senff@...

The address is there for spammers to harvest. - On 2002.05.08 21:04 Matt Armstrong wrote:
> I'm working through some of the exercises available in the O'Reily

@ is O(n), so the whole function is O(n^2).

> book that is available online at <http://caml.inria.fr/oreily-book/>.

>

> Here is what I came up with for a function that merges two lists. But

> I wonder if it is the best solution. It seems like the (accum @

> [element]) operations would be O(n) and so the whole function O(n^2).

> Or is the @ operator O(1)?

> Also, I'm doing a match on (a, b) -- is creating a tuple just for

It _is_ smart enough!

> pattern matching inefficient? Or is ocaml smart enough to not

> actually allocate memory for the tuple?

> Are there any alternative ways this function could be written short of

Why not

> replacing the pattern matches with a bunch of if/then expressions?

>

> (* write a function merge_i which takes as input two integer lists sorted

> in increasing order and returns a new sorted list containing the

> elements of the first two. *)

> let merge_i a b =

> let rec merge a b accum = match (a, b) with

> ([], []) -> accum

> | ([], head::tail) -> merge [] tail (accum @ [head])

| ([], _) -> b

?

> | (head::tail, []) -> merge [] tail (accum @ [head])

One optimization would be to accumulate by "head :: accum" instead of

> | (ahead::atail, bhead::btail) ->

> if ahead < bhead then

> merge atail b (accum @ [ahead])

> else

> merge a btail (accum @ [bhead])

> in

> merge a b []

> ;;

"accum @ [head]", and to reverse the resulting list afterwards (List.rev

is O(n), and tail-recursive). The temporary extra space and the extra time

can be ignored as long as the list is not bigger than the minor heap (32k

words, every list cell takes 3 words, so lists up to 32k/3 cells are "short").

Longer lists would be at least partly stored in the major heap, and collecting

these cells after usage is rather expensive (more expensive than

the operation List.rev itself).

Gerd

--

----------------------------------------------------------------------------

Gerd Stolpmann Telefon: +49 6151 997705 (privat)

Viktoriastr. 45

64293 Darmstadt EMail: gerd@...

Germany

---------------------------------------------------------------------------- - --- In ocaml_beginners@y..., Gerd Stolpmann <info@g...> wrote:
>

Good to know.

> @ is O(n), so the whole function is O(n^2).

> > Also, I'm doing a match on (a, b) -- is creating a tuple just for

Also good to know! :-)

> > pattern matching inefficient? Or is ocaml smart enough to not

> > actually allocate memory for the tuple?

>

> It _is_ smart enough!

Actually I finally realized you can do it in this more

efficient way:

let rec merge_i a b = match (a, b) with

([], _) -> b

| (_, []) -> a

| (ahead::atail, bhead::btail) ->

if ahead < bhead then

ahead :: merge_i atail b

else

bhead :: merge_i a btail