From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 AB6CEBC75 for ; Tue, 22 Feb 2005 10:07:45 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j1M97jh9014031 for ; Tue, 22 Feb 2005 10:07:45 +0100 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id KAA27421 for ; Tue, 22 Feb 2005 10:07:44 +0100 (MET) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j1M97ivW019053 for ; Tue, 22 Feb 2005 10:07:44 +0100 Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.11/jtpda-5.4) with ESMTP id j1M97hem051274 for ; Tue, 22 Feb 2005 10:07:44 +0100 (CET) X-Ids: 168 Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id KAA21576 for ; Tue, 22 Feb 2005 10:04:48 +0100 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id KAA909512 for ; Tue, 22 Feb 2005 10:06:32 +0100 X-Authentication-Warning: ibm1.cicrp.jussieu.fr: fernande owned process doing -bs Date: Tue, 22 Feb 2005 10:06:31 +0100 (NFT) From: Diego Olivier Fernandez Pons X-X-Sender: fernande@ibm1 To: caml-list@inria.fr Subject: Re: [Caml-list] Persistence In-Reply-To: <200502212324.11937.jon@jdh30.plus.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-1.7.2 (shiva.jussieu.fr [134.157.0.168]); Tue, 22 Feb 2005 10:07:44 +0100 (CET) X-Miltered: at concorde with ID 421AF661.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 421AF660.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 421AF660.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Spam: no; 0.00; pons:01 pons:01 caml-list:01 intuitively:01 convincing:01 speed-ups:01 solvers:01 recursion:01 garbage:01 computations:01 garbage:01 low-level:01 winning:98 structures:01 structures:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: Bonjour, > > Could you send around the source code to this? I intuitively knew > > that such performance results were likely, but had never had such > > a convincing example to wave at people. > > Yes. The implementation of traveling salesman given in my book is > another example which is several orders of magnitude faster than the > C/C++/Fortran implementations given in all of the other text books > that I have read. Branch-and-bound algorithms (pure integer, not LP based) are good candidates for important speed-ups due to data persistence : when you backtrack it is most of the time much faster to restart from a memorized data structure than to reconstruct it, specially with structured data like ordered sets, graphs, etc. Generally speaking, the _good_ paradigm to program B&B solvers for NP-hard problems is mixed functional/imperative programming (in other words ML), because you benefit from fast recursion, data persistence, garbage collection while you use very few floating point computations. Actually, most of the commercial C/C++ libraries for constraint programming (= integer branch and bound) include a 'functional layer' that contains one or several garbage collectors, persistent data structures, a system to make persistent user-defined data structures, function objects, etc. Winning against a mixed imperative/functional implementation in e.g. C/C++ require a lot of low-level implementation work - and you will end anyway implementing some kind of 'functional core'. Worse, algorithmic wins (better algorithms) are most of the time several order of magnitude superior than implementation wins (better implementation). Therefore it is also more convenient to use a high level language like Caml in order to focalize on algorithms rather than implementation. Diego Olivier