On Wednesday 28 December 2005 16:42, Ciaran McCreesh wrote: > On Wed, 28 Dec 2005 16:36:28 +0100 Paul de Vrieze <[EMAIL PROTECTED]> > > wrote: > | 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. > > Lookups against the tree can be done in O(1) time. That isn't the > issue. The issue is that as soon as you introduce backtracking, you go > to O(n!) with a general "try stuff in order" algorithm like the one > you proposed, which for 1000 packages is utterly unusable.
Only O(n!) in the worst case. As currently the algorithm does not do backtracking it has a O(n) complexity in the number of packages. With the current tree, backtracing should never be needed, so in practice nothing is left from that O(n!) complexity. The only case for worst case complexity is when the matching doesn't work. What we need for that is smart backtracking. We should recognize that if version A fails the dependency check, then version B can only fix that if it's dependencies differ. And only for those dependencies that are different. I'm not clear yet exactly how to do it, but it should go along those lines. Paul -- Paul de Vrieze Gentoo Developer Mail: [EMAIL PROTECTED] Homepage: http://www.devrieze.net
pgpgGzsh90koY.pgp
Description: PGP signature
