Re: [Caml-list] Question on writing efficient Ocaml.

[Jon Harrop <jon@ffconsultancy.com>]

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