[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

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  

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: