[ANN] constraint-0.2

[Alexandre Fayolle]

Magnus Lie Hetland a écrit :
> In article <mailman.1023468735.788.python-list at python.org>, Alexandre wrote:
>>How well does it perform?
>> * 8-queens problems solved in 15 seconds on my 1GHz PC
> 
> Interesting... The package looks really cool, but the performance in
> this example is truly abysmal. The simple queens.py found in the
> standard Python distribution solves the 8-queens problem (finds all
> solutions) in 0.11 seconds on an 800MHz PC. I guess maybe that't the
> price you have to pay for generality... On the other hand, a speedup
> factor of well over 100 seems to indicate a potential for
> streamlining... Maybe?

I do agree to all of this.

As you said, your comparison is not fair at all ;o), because 
Demo/scripts/queens.py  is targeted specifically at the n-queens
problem.

<tong-in-cheek mode="on">
Please note that if your main interest is solving the N-queens
problems, searchers have found an O(N) algorithm that will certainly
perform much better than queens.py in the Python distribution.
</tong-in-cheek>

Now, seriously.

This script uses a simple backtracking approach and shows that
it can be very efficient with some problems. The constraint package uses
a different approach (constraint propagation), which is supposed to be 
*at least* as efficient as backtracking, in terms of algorithmic
complexity.

So how comes the constraint package doesn't toast the backtracking
approach?
 * the example solution in the constraint package uses the constraint
 class MathematicConstraint which deals with arbitrary N-ary mathematic
 constraint. I can write an subclass optimized for binary constraints,
 which are the only thing we need for n-queens
 * the constraint package adds some overhead in processing constraint
 queues, and it is possible that some of the inner structures are not
 efficient. Blame this on the young age of the package.
 * maybe there is some horribly inneficient code in my package that I
 haven't seen yet. Be assured that as soon as I spot it, it will get
 refactored.

It's nice to have a comparison anyway. It helps to get an idea of what
our target is. Just as a sidenote, the very first (unreleased) version
of the package took 35 minutes to solve the 8 queens problem, so I
already got a 140x speed increase. Achieving another 140x speed increase
will certainly be harder, but it's nothing out of reach. 

And then, once constraint-1.0 is considered stable, maybe will go for a
rewrite in C.

> - Magnus (who hasn't looked at the internals, and who looks forward to
>   playing around with the package :)

Please do so, and join us on the python-logic mailing list.
http://lists.logilab.org/mailman/listinfo/python-logic

Alexandre Fayolle
-- 
LOGILAB, Paris (France).
http://www.logilab.com   http://www.logilab.fr  http://www.logilab.org
Narval, the first software agent available as free software (GPL).