| 1 |
On Tuesday 27 December 2005 18:37, Carsten Lohrke wrote: |
| 2 |
> On Tuesday 27 December 2005 18:07, Ciaran McCreesh wrote: |
| 3 |
> > It's worse than O(n^n) if you try to do USE dep conflict resolution |
| 4 |
> > too... |
| 5 |
> |
| 6 |
> Theoretically yes, practically the worst number of dependency levels we |
| 7 |
> speak of to walk up/down is not infinite ;). Of course there's no chance to |
| 8 |
> get this linear (speak: walking down the dependencies once), unless you |
| 9 |
> store the information which ebuild depends (or more exactly DEPENDs && |
| 10 |
> RDEPENDs) on foo in a list in foo's pkg db entry. The dependency resolution |
| 11 |
> of the packages needed to rebuild on top of it is not different as usual. |
| 12 |
|
| 13 |
It's never linear. Changing n doesn't make it so. It just circumventing the |
| 14 |
problem. And what is "n" here exactly. I'd guess the average number of |
| 15 |
dependencies of a package. This does however not say anything about the depth |
| 16 |
of the tree. We can now however that in most cases based from an empty tree |
| 17 |
(or only a very minimal tree) the total number of packages (and as such |
| 18 |
dependencies) is less than 1000. A number that is well manageable. |
| 19 |
|
| 20 |
The problem is caused by packages being dependencies from multiple sides. The |
| 21 |
trick is that if a package is pulled in by one side it should be taken for |
| 22 |
granted by the other side if it satisfies it's dependencies. Detecting that |
| 23 |
can be done by hashtables which have O(log n) complexity on the number of |
| 24 |
packages in the tree. In any case not that expensive. |
| 25 |
|
| 26 |
Paul |
| 27 |
|
| 28 |
-- |
| 29 |
Paul de Vrieze |
| 30 |
Gentoo Developer |
| 31 |
Mail: pauldv@g.o |
| 32 |
Homepage: http://www.devrieze.net |
Archives