[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2005-02-22 (09:07) |
From: | Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@e...> |
Subject: | Re: [Caml-list] Persistence |
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