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

[Andrej Bauer <Andrej.Bauer@fmf.uni-lj.si>]

[-- Attachment #1: Type: text/plain, Size: 2051 bytes --]

Dear Ian,

your ocaml code is quite "unusual", and I must say I am not convinced 
your C++ code is written optimally (but I don't know anything about C++).

I transcribed your C++ version to a reasonable ocaml version. Please 
compare what you did with how I transliterated your C++ code (attached 
file queen.ml). In particular, I use more obvious types (position is 
just int*int, a board is a 2D array)

Then I wrote my own ocaml version which mimicks your algorithm, except 
that instead of creating new boards all the time, it just keeps a list 
of current positions of queens (attached file queen2.ml).

By the way, why are you placing 8 queens on the board, no matter how 
large the board is? I thought the idea was to put n queens on a board of 
size n x n.

The results are as follows. To compute 5000 times the solution for board 
size 8:
- your C++ takes:   4.055s
- your ocaml takes: 550s
- my transliteration queen.ml of your C++ takes: 46.603s
- my improved version queen2.ml takes: 25.483s

So, for a small board size your C++ wins over ocaml by a factor of 11.5 
(or just 6.28 if I am allowed to use a reasonable representation of 
boards). Also note how my ocaml transliteration is more than 10 times 
faster than yours (you did indeed write odd code). Someone on the list 
might suggest some further improvements to queen.ml.

Since your C++ copies around a lot of boards, it loses drastically 
against the improved ocaml version when the board size goes up. For 
example, at board size 100 your C++ is 10 times slower than my ocaml 
queen2.ml, but this comparison is not fair, as I changed the data 
structure. You should implement a C++ version that uses a list of queen 
positions to represent the board and compare against queen2.ml.

Oh, by the way, C++ loses in code size (but this is well known in general):
- your C++ is 161 lines (3849 bytes)
- the ocaml transliteration of your C++ is 79 lines (1870 bytes)
- my improved ocaml version is 58 lines (1472 butes).

Feel free to post this on your blog.

Best regards,

Andrej


[-- Attachment #2: queen.ml --]
[-- Type: application/x-forcedownload, Size: 1870 bytes --]

[-- Attachment #3: queen2.ml --]
[-- Type: application/x-forcedownload, Size: 1473 bytes --]