From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=disabled version=3.1.3 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id BB34FBC0B for ; Thu, 28 Dec 2006 17:28:50 +0100 (CET) Received: from pih-relay06.plus.net (pih-relay06.plus.net [212.159.14.133]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id kBSGSnfM022156 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO) for ; Thu, 28 Dec 2006 17:28:50 +0100 Received: from [80.229.56.224] (helo=[10.0.0.5]) by pih-relay06.plus.net with esmtp (Exim) id 1Gzy7d-0001TP-BQ for caml-list@yquem.inria.fr; Thu, 28 Dec 2006 16:28:49 +0000 From: Jon Harrop Organization: Flying Frog Consultancy Ltd. To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Question on writing efficient Ocaml. Date: Thu, 28 Dec 2006 16:26:37 +0000 User-Agent: KMail/1.9.5 References: In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-15" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200612281626.38328.jon@ffconsultancy.com> X-Miltered: at concorde with ID 4593F0C2.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ocaml:01 ocaml:01 verbose:01 ocamlopt:01 -noassert:01 -unsafe:01 ocamlopt:01 frog:98 wrote:01 assertions:01 caml-list:01 int:01 int:01 coords:97 data:02 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