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