On Fri, Mar 15, 2002 at 07:14:44AM -0800, Randolph Chung wrote:
> > > 2. Ideally one might want to recursively list all the dependents of build-
> > > dependencies too, but that is probably too expensive to compute.
> > On my Pentium 166MHz, the following command took about 10s (real) to
> > run, with devscripts (>= 2.6.90) installed:
>
> Thanks, that was good to know.
>
> one problem is that some packages have build-dependency chains that
> when resolved completely are very deep, and sometimes contains dependency
> cycles. One could argue that these are bugs, but they seem difficult to fix
> in some cases.
>
> As reference, here is an old build-dependency graph for bash:
> http://people.debian.org/~tausq/bash-build-deps.png (559k)
The current bash only takes about 7-8 seconds. Dependency cycles are
not a problem with my code: once a package is recorded as being a
dependency, it's dependencies are added to a "to-be-processed" list,
and then it is skipped if it is seen again. The "to-be-processed list
is ... well, processed. So my guess it that its time complexity is
approximately linear in the size of the status file and the total
number of dependencies. Replacing status with available so I can test
some packages with more dependencies, I have not noticed a significant
difference between bash (5 dependencies including itself) and gcompris
(40 dependencies). If you can find a bigger one easily, I'll test
that too!
Julian
--
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Julian Gilbey, Dept of Maths, Debian GNU/Linux Developer
Queen Mary, Univ. of London see http://people.debian.org/~jdg/
http://www.maths.qmul.ac.uk/~jdg/ or http://www.debian.org/
Visit http://www.thehungersite.com/ to help feed the hungry
