On Tue, Jul 12, 2005 at 07:08:50PM +0200, Robert Lemmen wrote: >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! I'll probably be in touch soon... :-) Yes, there is space for much more intelligent package sorting. The most important thing is to minimise the number of CDs/DVDs as much as possible. >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? Covered separately... -- Steve McIntyre, Cambridge, UK. steve@einval.com There's no sensation to compare with this Suspended animation, A state of bliss
Attachment:
signature.asc
Description: Digital signature