Re: MSDOS name conversion
dwarf@polaris.net (Dale Scheetz) wrote on 13.02.96 in <Pine.LNX.3.91.960213152151.2099E-100000@dwarf.polaris.net>:
> On 13 Feb 1996, Kai Henningsen wrote:
> > Well, the solution I've used in the past - and which has worked rather
> > well - is simply to copy the files from the largest to the smallest,
> > omitting any that won't fit, then take the next floppy.
> When I have done this in the past, if it consumes more than a few disks,
> I do a second pass once the file size has gotten down to a few K. At this
> point I take the first disk (which has substantial WRT 1K free space) and
> copy as many files as will fit, moving to the next disk until complete.
You seem not to have understood my recipe. With it, such a second pass
would find nothing that fits, because everything that fits is already
there.
I'll give an example. Suppose we have files of size 10, 9, ..., 1 and
disks of size 12.
My recipe gives
Disk\File 10 9 8 7 6 5 4 3 2 1 Free
1 x x 0
2 x x 0
3 x x 0
4 x x 0
5 x x 5
(In this special case, it's even optimal, because all the disks but the
last one get filled completely. That's not always true, of course.
However, I do get a lot disks with "0 bytes free" from my algorithm.)
For disk 1, we get: 10 fits, 9 doesn't so gets skipped, same until we get
to 2 which fits, 1 of course doesn't. And so on for the other disks.
However the pieces to begin with, the space left is always less than the
smallest remaining file, because otherwise that file would already have
gone on the disk.
This gets suboptimal if it would be better to replace a big file and very
little room with a bunch of smaller files and even less free room,
something which seems to happen seldom enough as to make no practical
difference in Real Life[tm] - I couldn't find an example showing this
without trying longer than a few minutes. So I consider this algorithm
"good enough".
Sorry. That's probably my math education showing [off].
MfG Kai
Reply to: