[Distutils] name of the dependency problem

[David Cournapeau]

On Wed, Apr 15, 2015 at 11:32 AM, Trishank Karthik Kuppusamy <
trishank at nyu.edu> wrote:

> On 15 April 2015 at 11:15, David Cournapeau <cournape at gmail.com> wrote:
>
>>
>> This is indeed the case. If you want to solve dependencies in a way that
>> works well, you want an index that describes all your available package
>> versions.
>>
>> While solving dependencies is indeed NP complete, they can be fairly fast
>> in practice because of various specificities : each rule is generally only
>> a few variables, and the rules have a specific form allowing for more
>> efficient rule representation (e.g. "at most one of variable", etc...). In
>> my experience, it is not more difficult than using graph-based algorithms,
>> and
>>
>> FWIW, at Enthought, we are working on a pure python SAT solver for
>> resolving dependencies, to solve some of those issues. I am actually
>> hacking on it right at PyCon, we hope to have a first working version end
>> of Q2, at which point it will be OSS, and reintegrated in my older project
>> depsolver (https://github.com/enthought/depsolver).
>>
>>
> Awesome! Then pip could use that in the near future :)
>

That's the goal. For various reasons, it ended up easier to develop the
solver within our own package manager enstaller, but once done, extracting
it as a separate library should not be too hard. It is for example designed
to support various versioning schemes (for legacy reasons we can't use
PEP440 just yet).

Regarding speed, initial experiments showed that even for relatively deep
graphs, the running time is taken outside the SAT solver (e.g. to generate
the rules, you need to parse the version of every package you want to
consider, and parsing 1000s of PEP440 versions is slow :) ).

David
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/distutils-sig/attachments/20150415/1d3f6a3e/attachment.html>