| 1 |
On Wednesday 28 December 2005 16:42, Ciaran McCreesh wrote: |
| 2 |
> On Wed, 28 Dec 2005 16:36:28 +0100 Paul de Vrieze <pauldv@g.o> |
| 3 |
> |
| 4 |
> wrote: |
| 5 |
> | The problem is caused by packages being dependencies from multiple |
| 6 |
> | sides. The trick is that if a package is pulled in by one side it |
| 7 |
> | should be taken for granted by the other side if it satisfies it's |
| 8 |
> | dependencies. Detecting that can be done by hashtables which have |
| 9 |
> | O(log n) complexity on the number of packages in the tree. In any |
| 10 |
> | case not that expensive. |
| 11 |
> |
| 12 |
> Lookups against the tree can be done in O(1) time. That isn't the |
| 13 |
> issue. The issue is that as soon as you introduce backtracking, you go |
| 14 |
> to O(n!) with a general "try stuff in order" algorithm like the one |
| 15 |
> you proposed, which for 1000 packages is utterly unusable. |
| 16 |
|
| 17 |
Only O(n!) in the worst case. As currently the algorithm does not do |
| 18 |
backtracking it has a O(n) complexity in the number of packages. With the |
| 19 |
current tree, backtracing should never be needed, so in practice nothing is |
| 20 |
left from that O(n!) complexity. The only case for worst case complexity is |
| 21 |
when the matching doesn't work. What we need for that is smart backtracking. |
| 22 |
We should recognize that if version A fails the dependency check, then |
| 23 |
version B can only fix that if it's dependencies differ. And only for those |
| 24 |
dependencies that are different. I'm not clear yet exactly how to do it, but |
| 25 |
it should go along those lines. |
| 26 |
|
| 27 |
Paul |
| 28 |
|
| 29 |
-- |
| 30 |
Paul de Vrieze |
| 31 |
Gentoo Developer |
| 32 |
Mail: pauldv@g.o |
| 33 |
Homepage: http://www.devrieze.net |
Archives