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=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 6E938BC0B for ; Fri, 29 Dec 2006 02:23:05 +0100 (CET) Received: from postar.fmf.uni-lj.si (vega.fmf.uni-lj.si [193.2.67.45]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id kBT1N4HP004939 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Fri, 29 Dec 2006 02:23:05 +0100 Received: from localhost (unknown [192.168.5.1]) by postar.fmf.uni-lj.si (Postfix) with ESMTP id 269E5F62D9; Fri, 29 Dec 2006 02:23:04 +0100 (CET) X-Virus-Scanned: amavisd-new at spam.fmf.uni-lj.si Received: from postar.fmf.uni-lj.si ([192.168.5.5]) by localhost (spam.fmf.uni-lj.si [192.168.5.1]) (amavisd-new, port 10024) with ESMTP id xkr5CYHzcKVk; Fri, 29 Dec 2006 02:32:10 +0100 (CET) Received: from [192.168.1.100] (BSN-77-186-71.dsl.siol.net [193.77.186.71]) by postar.fmf.uni-lj.si (Postfix) with ESMTP id 7822BF6213; Fri, 29 Dec 2006 02:23:03 +0100 (CET) Message-ID: <45946E13.20708@fmf.uni-lj.si> Date: Fri, 29 Dec 2006 02:23:31 +0100 From: Andrej Bauer Reply-To: Andrej.Bauer@andrej.com User-Agent: Thunderbird 1.5.0.7 (X11/20060927) MIME-Version: 1.0 To: Ian Oversby , caml-list@yquem.inria.fr Subject: Re: [Caml-list] Question on writing efficient Ocaml. References: In-Reply-To: Content-Type: multipart/mixed; boundary="------------080005070005030900030008" X-Miltered: at concorde with ID 45946DF8.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; andrej:01 andrej:01 ocaml:01 ocaml:01 blog:98 wrote:01 slower:01 caml-list:01 algorithm:01 int:01 int:01 data:02 bytes:03 bytes:03 ian:03 X-Attachments: cset="ISO-8859-2" type="application/x-forcedownload" name="queen.ml" name="queen.ml" type="application/x-forcedownload" name="queen2.ml" name="queen2.ml" This is a multi-part message in MIME format. --------------080005070005030900030008 Content-Type: text/plain; charset=ISO-8859-2; format=flowed Content-Transfer-Encoding: 7bit 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 --------------080005070005030900030008 Content-Type: application/x-forcedownload; name="queen.ml" Content-Transfer-Encoding: base64 Content-Disposition: inline; filename="queen.ml" dHlwZSBzcXVhcmUgPSBRdSB8IFNhZmUgfCBBdAoKKCogQSBib2FyZCBpcyBhbiBhcnJheSBv ZiBhcnJheXMgb2Ygc3F1YXJlcyAqKQp0eXBlIGJvYXJkID0gc3F1YXJlIGFycmF5IGFycmF5 Cgp0eXBlIHBvc24gPSBpbnQgKiBpbnQKCmxldCBzdHJpbmdfb2Zfc3F1YXJlID0gZnVuY3Rp b24KICB8IFF1ICAgLT4gIlF1IgogIHwgU2FmZSAtPiAiI2YiCiAgfCBBdCAgIC0+ICJBdCIK CmxldCBpbml0X3BvcyA9ICgwLDApCgpsZXQgZ2V0IGJvYXJkICh4LHkpID0gYm9hcmQuKHkp Lih4KQoKbGV0IGRpc3BsYXkgYm9hcmQgPQogIEFycmF5Lml0ZXIKICAgIChmdW4gcm93IC0+ CiAgICAgICBBcnJheS5pdGVyIChmdW4gc3F1YXJlIC0+IHByaW50X3N0cmluZyAoc3RyaW5n X29mX3NxdWFyZSBzcXVhcmUgXiAiICIpKSByb3cgOwogICAgICAgcHJpbnRfbmV3bGluZSAo KQogICAgKQogICAgYm9hcmQKICAKbGV0IGJ1aWxkIHNpemUgZiA9CiAgQXJyYXkuaW5pdCBz aXplIChmdW4geSAtPiBBcnJheS5pbml0IHNpemUgKGZ1biB4IC0+IGYgKHgseSkpKQoKbGV0 IGlzX3RocmVhdGVuZWQgKHgxLHkxKSAoeDIseTIpID0KICB4MSA9IHgyIHx8IHkxID0geTIg fHwgKHgyIC0geDEpID0gKHkyIC0geTEpIHx8ICh4MSAtIHkyKSA9ICh4MiAtIHkxKQoKbGV0 IGFkZF9xdWVlbiBib2FyZCBwID0KICBidWlsZAogICAgKEFycmF5Lmxlbmd0aCBib2FyZCkK ICAgIChmdW4gcSAtPgogICAgICAgaWYgcSA9IHAgdGhlbgoJIFF1CiAgICAgICBlbHNlCgkg bWF0Y2ggZ2V0IGJvYXJkIHEgd2l0aAoJICAgfCBTYWZlIHdoZW4gaXNfdGhyZWF0ZW5lZCBx IHAgLT4gQXQKCSAgIHwgc3F1YXJlIC0+IHNxdWFyZSkKCmV4Y2VwdGlvbiBOb19zb2x1dGlv bgoKKCogVGhpcyBmdW5jdGlvbiBpcyB0aGUgZXF1aXZhbGVudCBvZiBCb2FyZDo6cGxhY2Vt ZW50LiAqKQpsZXQgcmVjIHNvbHZlIGJvYXJkIHAgcmVtID0KICBsZXQgc2l6ZSA9IEFycmF5 Lmxlbmd0aCBib2FyZCBpbgogIGxldCBuZXh0X3Bvc24gKHB4LF8pICh4LHkpID0KICAgICAg aWYgeCArIDEgPCBzaXplIHRoZW4gKHgrMSwgeSkKICAgICAgZWxzZSBpZiB5ICsgMSA8IHNp emUgdGhlbiAocHgsIHkrMSkKICAgICAgZWxzZSByYWlzZSBOb19zb2x1dGlvbgogIGluCQog IGxldCBuZXh0X3ZhbGlkX3Bvc24gcCA9CiAgICBsZXQgcmVjIGxvb3AgcSA9CiAgICAgIG1h dGNoIGdldCBib2FyZCBxIHdpdGgKCXwgU2FmZSAtPiBxCgl8IF8gLT4gbG9vcCAobmV4dF9w b3NuIHAgcSkKICAgIGluCiAgICAgIGxvb3AgcAogIGluCQogICAgaWYgcmVtID0gMCB0aGVu CiAgICAgIGJvYXJkCiAgICBlbHNlCiAgICAgIGxldCBwJyA9IG5leHRfdmFsaWRfcG9zbiBw IGluCgl0cnkKCSAgc29sdmUgKGFkZF9xdWVlbiBib2FyZCBwJykgaW5pdF9wb3MgKHJlbS0x KQoJd2l0aCBOb19zb2x1dGlvbiAtPiBzb2x2ZSBib2FyZCAobmV4dF9wb3NuIHAgcCcpIHJl bQoKbGV0IG1haW4gPQogIHRyeQogICAgbGV0IHNpemUgPSBpbnRfb2Zfc3RyaW5nIFN5cy5h cmd2LigxKSBpbgogICAgbGV0IHRpbWVzID0gaW50X29mX3N0cmluZyBTeXMuYXJndi4oMikg aW4KICAgIGxldCBlbXB0eV9ib2FyZCA9IGJ1aWxkIHNpemUgKGZ1biBfIC0+IFNhZmUpIGlu CiAgICAgIGZvciBpID0gMiB0byB0aW1lcyBkbwoJaWdub3JlIChzb2x2ZSBlbXB0eV9ib2Fy ZCAoMCwwKSA4KQogICAgICBkb25lIDsKICAgICAgZGlzcGxheSAoc29sdmUgZW1wdHlfYm9h cmQgKDAsMCkgOCkKICB3aXRoIAogICAgfCBOb19zb2x1dGlvbiAtPiBwcmludF9lbmRsaW5l ICJObyBzb2x1dGlvbi4iCiAgICB8IF8gLT4gcHJpbnRfZW5kbGluZSAoIlVzYWdlOiAiIF4g U3lzLmFyZ3YuKDApIF4gIiBbc2l6ZV0gW3RpbWVzXSIpCg== --------------080005070005030900030008 Content-Type: application/x-forcedownload; name="queen2.ml" Content-Transfer-Encoding: base64 Content-Disposition: inline; filename="queen2.ml" KCogQSBib2FyZCBpcyByZXByZXNlbnRlZCBieSBhIGxpc3Qgb2YgcG9zaXRpb25zIG9mIHF1 ZWVucy4gKikKdHlwZSBwb3NpdGlvbiA9IGludCAqIGludAoKdHlwZSBib2FyZCA9IHBvc2l0 aW9uIGxpc3QKCigqIElzIHBvc2l0aW9uIHAgb24gYm9hcmQgYiBzYWZlPyAqKQpsZXQgc2Fm ZSBiICh4MSx5MSkgPQogIExpc3QuZm9yX2FsbAogICAgKGZ1biAoeDIseTIpIC0+IHgxIDw+ IHgyICYmIHkxIDw+IHkyICYmICh4MiAtIHgxKSA8PiAoeTIgLSB5MSkgJiYgKHgxIC0geTIp IDw+ICh4MiAtIHkxKSkKICAgIGIKCmxldCBkaXNwbGF5IG4gYiA9CiAgZm9yIHkgPSAwIHRv IG4gLSAxIGRvCiAgICBmb3IgeCA9IDAgdG8gbiAtIDEgZG8KICAgICAgbGV0IHAgPSAoeCx5 KSBpbgoJaWYgTGlzdC5tZW0gcCBiIHRoZW4gcHJpbnRfc3RyaW5nICJRdSAiCgllbHNlIGlm IHNhZmUgYiBwIHRoZW4gcHJpbnRfc3RyaW5nICIjZiAiCgllbHNlIHByaW50X3N0cmluZyAi QXQgIgogICAgZG9uZSA7CiAgICBwcmludF9uZXdsaW5lICgpCiAgZG9uZQoKKCogUGxhY2Ug YSBxdWVlbiBhdCBwb3NpdGlvbiBwIG9uIGJvYXJkIGIgKikKbGV0IHBsYWNlX3F1ZWVuIGIg cCA9IHAgOjogYgoKZXhjZXB0aW9uIE5vX3NvbHV0aW9uCgooKiBGaW5kIGEgbm9uLWF0dGFj a2luZyBjb25maWd1cmF0aW9uIG9mIGsgcXVlZW5zIG9uIGJvYXJkIG9mIHNpemUgbi4gKikK bGV0IHNvbHZlIG4gayA9CiAgbGV0IG5leHQgKHUsXykgKHgseSkgPQogICAgICBpZiB4ICsg MSA8IG4gdGhlbiAoeCsxLHkpCiAgICAgIGVsc2UgaWYgeSArIDEgPCBuIHRoZW4gKHUsIHkr MSkKICAgICAgZWxzZSByYWlzZSBOb19zb2x1dGlvbgogIGluCQogIGxldCByZWMgc29sdmUg YiBwIGsgPQogICAgbGV0IHJlYyBuZXh0X3NhZmUgcCA9CiAgICAgIGxldCByZWMgbG9vcCBx ID0gaWYgc2FmZSBiIHEgdGhlbiBxIGVsc2UgbG9vcCAobmV4dCBwIHEpIGluIGxvb3AgcAog ICAgaW4KICAgICAgaWYgayA9IDAgdGhlbgoJYgogICAgICBlbHNlCglsZXQgcCcgPSBuZXh0 X3NhZmUgcCBpbgoJICB0cnkKCSAgICBzb2x2ZSAocGxhY2VfcXVlZW4gYiBwJykgKDAsMCkg KGstMSkKCSAgd2l0aAoJICAgICAgTm9fc29sdXRpb24gLT4gc29sdmUgYiAobmV4dCBwIHAn KSBrCiAgaW4KICAgIHNvbHZlIFtdICgwLDApIGsKCmxldCBtYWluID0KICB0cnkKICAgIGxl dCBuID0gaW50X29mX3N0cmluZyBTeXMuYXJndi4oMSkgaW4KICAgIGxldCBrID0gaW50X29m X3N0cmluZyBTeXMuYXJndi4oMikgaW4KICAgICAgZm9yIGkgPSAyIHRvIGsgZG8gaWdub3Jl IChzb2x2ZSBuIDgpIGRvbmUgOwogICAgICBkaXNwbGF5IG4gKHNvbHZlIG4gOCkKICB3aXRo CiAgICB8IE5vX3NvbHV0aW9uIC0+IHByaW50X2VuZGxpbmUgIk5vIHNvbHV0aW9uLiIKICAg IHwgXyAtPiBwcmludF9lbmRsaW5lICgiVXNhZ2U6ICIgXiBTeXMuYXJndi4oMCkgXiAiIFtz aXplXSBbdGltZXNdIikK --------------080005070005030900030008--