## Is this an optimal list merging function?

Expand Messages
• I m working through some of the exercises available in the O Reily book that is available online at . Here is what I came up
Message 1 of 3 , May 8, 2002
• 0 Attachment
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
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.
• ... @ is O(n), so the whole function is O(n^2). ... It _is_ smart enough! ... Why not ... ? ... One optimization would be to accumulate by head :: accum
Message 2 of 3 , May 8, 2002
• 0 Attachment
On 2002.05.08 21:04 Matt Armstrong wrote:
> 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)?

@ 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
> pattern matching inefficient? Or is ocaml smart enough to not
> actually allocate memory for the tuple?

It _is_ smart enough!

> 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

Why not
| ([], _) -> b
?

> merge atail b (accum @ [ahead])
> else
> merge a btail (accum @ [bhead])
> in
> merge a b []
> ;;

One optimization would be to accumulate by "head :: accum" instead of
"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
Germany
----------------------------------------------------------------------------
• ... Good to know. ... Also good to know! :-) Actually I finally realized you can do it in this more efficient way: let rec merge_i a b = match (a, b) with
Message 3 of 3 , May 8, 2002
• 0 Attachment
--- In ocaml_beginners@y..., Gerd Stolpmann <info@g...> wrote:
>
> @ is O(n), so the whole function is O(n^2).

Good to know.

> > 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?
>
> It _is_ smart enough!

Also good to know! :-)

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