olm@informatik.uni-kiel.dbp.de (Olaf Mehlberg) (03/15/91)
There is a somewhat different algorithm (with higher complexity but
better results) you can use, if the capacity of your floppy is not
very large (speak not more then 12 MByte). This is because you will
need an array of integer in the size of the free UNITS (one UNIT is
usually 1024 Bytes) on the disk.
Let us assume having two arrays :
filelength : array [ 1 .. number_of_files ] of 0 .. maxfilesize
containing the length of the files in units.
fileposition : array [ 1 .. size_of_disk_in_units ] of 1 .. number_of_files
initialized to zero.
and one integer last_index, initialized to zero, to denote the last
index in fileposition corresponding to a nonzero value.
Fill the fileposition-array with filenumbers according to the following
rules :
Assign the filenumber FN to fileposition[ I ] if :
(1.1) fileposition[ I - filelength[ FN ] ] is not zero and not FN
(occupied by another file)
AND
(1.2) fileposition[ I ] is zero ( not yet occupied )
After assigning all possible filepositions, do a last assignment
(1.3) fileposition[ filelength[ FN ] ] to FN if
fileposition[ filelength[ FN ] ] is equal to zero.
You have to do this (only once for each filenumber :-)) till
no file is left or last_index is equal to size of disk in units (then
you have reached the subgoal : a completely filled floppy)
Important point : How can we the filenumbers out of the fileposition-
array ?
(2.1) Copy the file with number fileposition[ last_index ]
onto the floppy.
(2.2) Decrement last_index by
filelength[ fileposition[ last_index ] ]
If last_index equals zero, you are ready; else proceed at (2.1)
I guarantee (hopefully :-) the existence of a chain from last_index to
zero with the restriction (1.1) above. ( and a non-zero value of
last_index with rule (1.3))
After copying the files, you have to delete them from the
filelength-array and apply the same algorithm to less files
(and a new floppy :-)).
Note the non-determinism in the election of the files. This
algorithm does not guarantee optimal results in all cases, but better
results then DFF. But it IS a good idea to sort the files by decreasing
length.
The example from Tim Margush leads to the following arrays
File-size 4 3 3 2 2 2 Disk size 8
File-number 1 2 3 4 5 6
1st run:
File-position : 3 2 1 3 3 2 4 index chain : 8 6 3 0 file-
index : 1 2 3 4 5 6 7 8 filenumbers : 4 3 2 sizes: 2 3 3
2nd run: with the remaining filenumbers 1 5 6
File-position : 5 1 5 6 index chain : 8 6 4 0 file-
index : 1 2 3 4 5 6 7 8 filenumbers : 6 5 1 sizes: 4 2 2
If anybody needs a more specific implementation, fell free to contact
me via e-mail. I will post the implementation if there is sufficent
interest (otherwise I e-mail it to you).
(Please dont forget to enclose a SASE in your e-mail 8-))
Olaf Mehlberg
**********************************************************************
** I would be pleased, if you send me the disks you saved with this **
** algorithm, but I do not send the additional used disks to you. **
----------------------------------------------------------------------
Christian-Albrechts-Universitaet Kiel, Institut fuer Informatik
Preusserstr. 1 - 9 , D - 2300 Kiel 1
Phone: ++49-431-5604-42 , Fax: ++49-431-566143
EMail: olm@informatik.uni-kiel.dbp.de
----------------------------------------------------------------------