On Tue, Jul 12, 2005 at 05:54:39PM +0300, Steve McIntyre wrote:
> 6. Actual layout of the CDs could be better
>
> At the moment, we guess how much space the docs/boot/tools
> etc. will take at the start of each CD run, then ask apt to fill
> up the available space. Then we run apt-ftparchive to generate the
> Packages and Sources files. This is not very accurate - a lot of
> the time during past releases has been taken up by manually
> juggling CD sizes to make them as large as possible without going
> over 650MB.
>
> A much better way would be to check sizes as each file is copied
> into the temporary tree, and Packages and Sources files generated
> by copying stanzas in to match. By keeping careful track of how
> much space the tree takes, once the tree gets to within a small
> margin of the target, we can start running mkisofs -print-size to
> check exactly how large the resulting image would be. It will even
> be possible to maximise the image size by simply running until a
> package/source file would take the image over the configured
> limit, then rolling back.
the downside to this approach is that if the last package (the one that
made the size go over the limit) is largish, you waste a lot of space.
on average that would be 1/2 the average package size (~250 kb) and in
the worst case the size of the largest package (~55 Mb). if we don't
want packages on disk n where dependencies are on disk n+m, then we
can't simply skip the large package and try to fill the space with
smaller packages later in the list. doing this for real would be trying
to solve an extended knapsack problem (np-hard). the "proper" way to
deal with something like this would be a meta.heurtistic like ant
systems or genetic algorithms (i have done that before), but i am very
confident that you can get pretty close with a simple heuristic like
this:
- order the packages as done up to now
- build a (reverse) directed graph of dependencies over the list
- loop until no packages left
- take the first package in the list that has no incoming edges
- check if it fits on the cd
- yes: put it there and delete all edges to/from it
- no: try the next package in the list
- if there are no packages in the list that have no incoming edges,
but there are still packages in the list: start a new cd
if you guys want this, give me an interface to hook it into and holler!
above you said:
> [...] once the tree gets to within a small
> margin of the target, we can start running mkisofs -print-size to
> check exactly how large the resulting image would be. It will even
is this really necessary? can't we somehow determine how much will fit
on the cd without doing this?
cu robert
--
Robert Lemmen http://www.semistable.com
Attachment:
signature.asc
Description: Digital signature