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

Question on writing efficient Ocaml.
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2006-12-28 (16:28) From: Jon Harrop Subject: Re: [Caml-list] Question on writing efficient Ocaml.
```On Thursday 28 December 2006 11:42, Ian Oversby wrote:
> Hi,
>
> Apologies if this is the wrong forum in which to ask this question.  Is
> there anywhere else more suitable?

Here is fine.

> I've written some Ocaml code to solve the problem of placing 8 queens on a
> board so that none of them attack each-other.  I've also written a C++
> equivalent which is running much more quickly than the Ocaml.

The programs are not equivalent. Profiling shows the C++ is calling
is_threatened 1,915 to get 1 solution whereas the OCaml is calling it 129,030
times.

So the algorithms are different.

The code is also needlessly verbose and inefficient. There's no point in
declaring sum types with one contructor:

type posn = Posn of int * int;;
type board = Board of square array * int;;

There is no need for pattern matches with only one pattern:

let is_threatened queen square =
match queen, square with
(x1, y1), (x2, y2) ->
x1 == x2 ||
y1 == y2 ||
(x2 - x1) == (y2 - y1) ||
(x1 - y2) == (x2 - y1);;

let is_threatened (x1, y1), (x2, y2) =
x1 == x2 || y1 == y2 || x2 - x1 == y2 - y1 || x1 - y2 == x2 - y1;;

The program is also convoluted, e.g. add_queen converts the same value to and
from index<->coords.

I'm not sure it is even worth having a board data structure. Why not have an
implicit board and a list of queen positions? I'll have a go...

> ocamlopt -noassert -unsafe -ccopt -O3 -ccopt -fomit-frame-pointer q.ml -o
> q.exe

Don't bother with the optimisation switches. Just use:

ocamlopt q.ml -o q

You don't have any assertions, bounds checking is insignificant and you're not
compiling any C code...

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

```