1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
|
<!--startcut ======================================================= -->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<META NAME="generator" CONTENT="lgazmail v1.4F.u">
<TITLE>The Answer Gang 80: How to optimize space usage for multiple files on multiple CDs</TITLE>
</HEAD><BODY BGCOLOR="#FFFFFF" TEXT="#000000"
LINK="#3366FF" VLINK="#A000A0">
<!--endcut ========================================================= -->
<P> <hr>
<!--startcut ======================================================= -->
<CENTER>
<!-- *** BEGIN navbar *** -->
<!-- *** END navbar *** -->
</CENTER>
</p>
<!--endcut ========================================================= -->
<!--startcut ======================================================= -->
<P> <hr>
<!-- begin tagnav ::::::::::::::::::::::::::::::::::::::::::::::::::-->
<p align="center">
<table width="100%" border="0"><tr>
<td align="right" valign="center"
><IMG ALT="" SRC="../../gx/navbar/left.jpg"
WIDTH="14" HEIGHT="45" BORDER="0" ALIGN="middle" border="0"
><A HREF="../index.html"
><IMG SRC="../../gx/navbar/toc.jpg" align="middle"
ALT="[ Table Of Contents ]" border="0"></A
><A HREF="../lg_answer.html"
><IMG SRC="../../gx/dennis/answertoc.jpg" align="middle"
ALT="[ Answer Guy Current Index ]" border="0"></A></td>
<td align="center" valign="center"><A HREF="../lg_answer.html#greeting"><img align="middle"
src="../../gx/dennis/smily.gif" alt="greetings" border="0"></A>
<A HREF="../tag/bios.html">Meet the Gang</A>
<A HREF="1.html">1</A>
<A HREF="2.html">2</A>
<A HREF="3.html">3</A>
<A HREF="4.html">4</A>
<A HREF="5.html">5</A>
<A HREF="6.html">6</A>
<A HREF="7.html">7</A>
</td>
<td align="left" valign="center"><A HREF="../../tag/kb.html"
><IMG SRC="../../gx/dennis/answerpast.jpg" align="middle"
ALT="[ Index of Past Answers ]" border="0"></A
><IMG ALT="" SRC="../../gx/navbar/right.jpg" align="middle"
WIDTH="14" HEIGHT="45" BORDER="0"></td></tr></table>
</p>
<!-- end tagnav ::::::::::::::::::::::::::::::::::::::::::::::::::::-->
<!--endcut ========================================================= -->
<P> <hr> <P>
<!-- ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: -->
<center>
<H1><A NAME="answer">
<img src="../../gx/dennis/qbubble.gif" alt="(?)"
border="0" align="middle">
<font color="#B03060">The Answer Gang</font>
<img src="../../gx/dennis/bbubble.gif" alt="(!)"
border="0" align="middle">
</A></H1>
<BR>
<H4>By Jim Dennis, Ben Okopnik, Dan Wilder, Breen, Chris, and...
(<a href="tag/bios.html">meet the Gang</a>) ...
the Editors of Linux Gazette...
and You!
<br>Send questions (or interesting answers) to
The Answer Gang
for possible publication
(but read the <a href="../tag/ask-the-gang.html">guidelines</a> first)
</H4>
</center>
<!-- ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: -->
<p><hr><p>
<!-- begin 7 -->
<H3 align="left"><img src="../../gx/dennis/qbubble.gif"
height="50" width="60" alt="(?) " border="0"
>How to optimize space usage for multiple files on multiple CDs</H3>
<p><strong>From Michiel van Leening
</strong></p>
<p align="right"><strong>Answered By Thomas Adam (The LG Weekend Mechanic), Ben Okopnik, Karl-Heinz Herrmann
</strong></p>
<blockquote><em><font color="#000066">With our kind thanks to Michiel for granting publication permission
<IMG SRC="../../gx/dennis/smily.gif" ALT=":)"
height="24" width="20" align="middle">
-- Heather</font></em></blockquote>
<P><STRONG>
Hi Gang,
</STRONG></P>
<P><STRONG>
I've got a bunch of files which will roughly fill up 12 CDR's. My question
is, how can i best optimize the space used for these files, so as to use as
little CD's as possible?
</STRONG></P>
<blockQuote>
<IMG SRC="../../gx/dennis/bbub.gif" ALT="(!)"
HEIGHT="28" WIDTH="50" BORDER="0"
> [Thomas]
Assumming that you are not fussed as to which files
appear on which CDR, and assuming that these files
reside in a single common directory, then you could
write a script that will take the largest files.
</blockQuote>
<blockQuote>
<IMG SRC="../../gx/dennis/bbub.gif" ALT="(!)"
HEIGHT="28" WIDTH="50" BORDER="0"
> [Ben]
Actually, that's an NP-Complete problem, i.e. you can't get an actual
solution before the Universe ends.
<IMG SRC="../../gx/dennis/smily.gif" ALT="<grin>"
height="24" width="20" align="middle"> Sad but true. However, there
are a number of "close enough" approximations you can do. I've never
heard of anyone scripting this kind of a thing, although I would imagine
every CS student out there has played with the concept.
</blockQuote>
<blockQuote>
Here's a reasonable one: sort your files. Grab the largest one, subtract
that from MAX_SIZE; now, find the largest file that will fit in the
remaining space. Iterate until the remaining space is smaller than your
smallest file. Repeat the above process for every one of your CDs.
You're done - and in linear time, too.
<IMG SRC="../../gx/dennis/smily.gif" ALT=":)"
height="24" width="20" align="middle">
</blockQuote>
<P><STRONG>
<IMG SRC="../../gx/dennis/qbub.gif" ALT="(?)"
HEIGHT="28" WIDTH="50" BORDER="0"
>
I've tried just looping through all the files and as long as the sum of the
already seen files stays below the CD size limit, the file is added to a list.
</STRONG></P>
<blockQuote>
<IMG SRC="../../gx/dennis/bbub.gif" ALT="(!)"
HEIGHT="28" WIDTH="50" BORDER="0"
> [Ben]
Erm... a 20MB file followed by a 631MB file, and you've got a CD with
20MB on it. Not a reasonable compromise. Even if you sort them first,
326+325, and you've wasted half a CD.
</blockQuote>
<P><STRONG>
<IMG SRC="../../gx/dennis/qbub.gif" ALT="(?)"
HEIGHT="28" WIDTH="50" BORDER="0"
>
As soon as a file goes above the size limit, it starts a new list with
filenames. These list are then used to burn the CD's with either mkisofs or
Gcombust.
</STRONG></P>
<blockQuote>
<IMG SRC="../../gx/dennis/bbub.gif" ALT="(!)"
HEIGHT="28" WIDTH="50" BORDER="0"
> [Thomas]
Is the limit 650 MB, in which case:
</blockQuote>
<p align="center">See attached <tt><a href="../misc/tag/fill-it-up.bash.txt">fill-it-up.bash.txt</a></tt></p>
<P><STRONG>
<IMG SRC="../../gx/dennis/qbub.gif" ALT="(?)"
HEIGHT="28" WIDTH="50" BORDER="0"
>
I'd actually like a program to figure out the best spread of files over the
CD's (eg. CD1 has files 3,5,8 and CD2 has files 1,2,4 and CD3 has files 6,7,9)
so as to minimize wasted space. What i've programmed myself has the
disadvantage that if the next file in line is big enough to cross the size
limit, it is put on the next CD, thereby wasting space on the current CD.
</STRONG></P>
<blockQuote>
<IMG SRC="../../gx/dennis/bbub.gif" ALT="(!)"
HEIGHT="28" WIDTH="50" BORDER="0"
> [Thomas]
I'll work on this at home
<IMG SRC="../../gx/dennis/smily.gif" ALT=":-)"
height="24" width="20" align="middle"> Might even put it in my
LWM article next month
<IMG SRC="../../gx/dennis/smily.gif" ALT=":-)"
height="24" width="20" align="middle">
</blockQuote>
<P><STRONG>
<IMG SRC="../../gx/dennis/qbub.gif" ALT="(?)"
HEIGHT="28" WIDTH="50" BORDER="0"
>
Now i could go and program such a thing, find out afterwards that something
like this exists and tear my hairs out in frustration. So, does a program
exist that can do this? Maybe someone has a script lying around. Ofcourse
intensive Googling for a week hasn't turned up anything.
</STRONG></P>
<P><STRONG>
Thanks for any input on the matter.
</STRONG></P>
<blockQuote>
<IMG SRC="../../gx/dennis/bbub.gif" ALT="(!)"
HEIGHT="28" WIDTH="50" BORDER="0"
> [Ben]
As I've mentioned, I haven't heard of anything (although any CompSci
department has seen thousands of attempts), but it shouldn't be all
<em>that</em> hard to script an approximation. The algorithm I suggested would
only take a few lines of Perl, and even a shell script wouldn't be all
that bad.
</blockQuote>
<blockQuote>
<IMG SRC="../../gx/dennis/bbub.gif" ALT="(!)"
HEIGHT="28" WIDTH="50" BORDER="0"
> [Thomas]
Hey Ben....you and I could work on this one
<IMG SRC="../../gx/dennis/smily.gif" ALT=":-)"
height="24" width="20" align="middle">
Whadaya reckon -- I'm sticking to bash !!
</blockQuote>
<blockQuote>
<IMG SRC="../../gx/dennis/bbub.gif" ALT="(!)"
HEIGHT="28" WIDTH="50" BORDER="0"
> [Ben]
<dryly> The actual scripting is left as an excercise to the student.
Gotta let folks do <em> _something</em> on their own, dude!
<IMG SRC="../../gx/dennis/smily.gif" ALT=":)"
height="24" width="20" align="middle">
</blockQuote>
<blockQuote>
Now, all I've got to do is figure out the purpose of your script,
above... what it does is obvious, <EM>why</EM> you'd care about the result
(if there <em> _was</em> any) isn't.
</blockQuote>
<blockQuote>
<IMG SRC="../../gx/dennis/bbub.gif" ALT="(!)"
HEIGHT="28" WIDTH="50" BORDER="0"
> [K.-H.]
Actually there is already a script which served me quite nicely. It's
already tied in with cdrekord and mkisofs and seems to handle special files
correctly (i.e. uisng cpio or something to dump them).
</blockQuote>
<blockQuote>
see:
</blockQuote>
<blockQuote><BLOCKQuote>
<A HREF="http://www.joat.ca/software/cddump.html"
>http://www.joat.ca/software/cddump.html</A>
</BLOCKQuote></blockQuote>
<P><STRONG>
<IMG SRC="../../gx/dennis/qbub.gif" ALT="(?)"
HEIGHT="28" WIDTH="50" BORDER="0"
>
That's excatly what i was looking for. Thanks a lot.
</STRONG></P>
<blockQuote>
<IMG SRC="../../gx/dennis/bbub.gif" ALT="(!)"
HEIGHT="28" WIDTH="50" BORDER="0"
> [Ben]
Cool; I figured somebody somewhere did it. Interestingly enough, he uses
pretty much the algorithm I suggested:
</blockQuote>
<blockquote><pre> @todo = sort { ${$b}[2] <=> ${$a}[2] } @todo;
...
foreach $file (@todo) {
if ($thissize + ${$file}[2] < $remaining) {
$thissize += ${$file}[2];
push(@{$thisdo[${$file}[0]]}, ${$file}[1]);
</pre></blockquote>
<blockQuote>
It's not a bad approximation; the only degenerate case is where you have
no-to-few small files and lots of large ( > MAX_SIZE/2 ) ones. If you
have an average file spread, it works well.
</blockQuote>
<!-- end 7 -->
<P> <hr> </p>
<!-- *** BEGIN copyright *** -->
<H5 align="center">This page edited and maintained by the Editors
of <I>Linux Gazette</I>
<a href=""
>Copyright ©</a> 2002
<BR>Published in issue 80 of <I>Linux Gazette</I> July 2002</H5>
<H6 ALIGN="center">HTML script maintained by
<A HREF="mailto:star@starshine.org">Heather Stern</a> of
Starshine Technical Services,
<A HREF="http://www.starshine.org/">http://www.starshine.org/</A>
</H6>
<!-- *** END copyright *** -->
<!--startcut ======================================================= -->
<P> <hr>
<!-- begin tagnav ::::::::::::::::::::::::::::::::::::::::::::::::::-->
<p align="center">
<table width="100%" border="0"><tr>
<td align="right" valign="center"
><IMG ALT="" SRC="../../gx/navbar/left.jpg"
WIDTH="14" HEIGHT="45" BORDER="0" ALIGN="middle" border="0"
><A HREF="../index.html"
><IMG SRC="../../gx/navbar/toc.jpg" align="middle"
ALT="[ Table Of Contents ]" border="0"></A
><A HREF="../lg_answer.html"
><IMG SRC="../../gx/dennis/answertoc.jpg" align="middle"
ALT="[ Answer Guy Current Index ]" border="0"></A></td>
<td align="center" valign="center"><A HREF="../lg_answer.html#greeting"><img align="middle"
src="../../gx/dennis/smily.gif" alt="greetings" border="0"></A>
<A HREF="../tag/bios.html">Meet the Gang</A>
<A HREF="1.html">1</A>
<A HREF="2.html">2</A>
<A HREF="3.html">3</A>
<A HREF="4.html">4</A>
<A HREF="5.html">5</A>
<A HREF="6.html">6</A>
<A HREF="7.html">7</A>
</td>
<td align="left" valign="center"><A HREF="../../tag/kb.html"
><IMG SRC="../../gx/dennis/answerpast.jpg" align="middle"
ALT="[ Index of Past Answers ]" border="0"></A
><IMG ALT="" SRC="../../gx/navbar/right.jpg" align="middle"
WIDTH="14" HEIGHT="45" BORDER="0"></td></tr></table>
</p>
<!-- end tagnav ::::::::::::::::::::::::::::::::::::::::::::::::::::-->
<!--endcut ========================================================= -->
<P> <hr>
<!--startcut ======================================================= -->
<CENTER>
<!-- *** BEGIN navbar *** -->
<!-- *** END navbar *** -->
</CENTER>
</p>
<!--endcut ========================================================= -->
<!--startcut ======================================================= -->
</BODY></HTML>
<!--endcut ========================================================= -->
|
