| 1 |
On Wed, 28 Dec 2005 16:36:28 +0100 Paul de Vrieze <pauldv@g.o> |
| 2 |
wrote: |
| 3 |
| The problem is caused by packages being dependencies from multiple |
| 4 |
| sides. The trick is that if a package is pulled in by one side it |
| 5 |
| should be taken for granted by the other side if it satisfies it's |
| 6 |
| dependencies. Detecting that can be done by hashtables which have |
| 7 |
| O(log n) complexity on the number of packages in the tree. In any |
| 8 |
| case not that expensive. |
| 9 |
|
| 10 |
Lookups against the tree can be done in O(1) time. That isn't the |
| 11 |
issue. The issue is that as soon as you introduce backtracking, you go |
| 12 |
to O(n!) with a general "try stuff in order" algorithm like the one |
| 13 |
you proposed, which for 1000 packages is utterly unusable. |
| 14 |
|
| 15 |
-- |
| 16 |
Ciaran McCreesh : Gentoo Developer (I can kill you with my brain) |
| 17 |
Mail : ciaranm at gentoo.org |
| 18 |
Web : http://dev.gentoo.org/~ciaranm |
Archives