Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!bloom-beacon!apple!chuq
From: chuq@Apple.COM (Chuq Von Rospach)
Newsgroups: comp.sys.mac
Subject: Re: Inefficiency with DiskFit 1.5 during backups
Keywords: Knapsack problem, NP-complete
Message-ID: <28902@apple.Apple.COM>
Date: 13 Apr 89 17:12:14 GMT
References: <1122@atux01.UUCP> <23539@coherent.com>
Organization: Life is just a Fantasy novel played for keeps
Lines: 38

>I'm not sure what algorithm DiskFit uses to decide how to group files
>together.

I've taken a look at what DiskFit seems to be doing, and while I don't have
the exact algorithm, I can make some educated guesses:

o Use as few floppies as possible.
o Don't split files unless necessary.
o Try to group the older (not recently modified) files together, so you
  don't get into the "I grew 5K, grab a new floppy" shuffle. 
o try to keep files in folders together.
o try to put a file back on the same floppy it came from.

Diskfit also tries to leave a little free space on a floppy, for two
reasons: one is to allow a file to grow slightly without having to move it
to a new floppy (thereby reducing fragmentation). It also needs to leave
room for the Desktop file that is created if you load the floppy from the
Finder (DiskFit will delete it when it sees it...).

>DiskFit could perhaps pack files more tightly together if it were
>willing to split even small files across multiple floppies.

Except that one design aspect of DiskFit I *really* like is that all of the
floppies are Finder readable -- the only backup utility to do so. This means
that I can go get a file, even if DiskFit throws up and dies on me. After
losing some files to HFS Backup 1.0 due to corruption, I'll happily toss in
a couple of extra floppies for this feature.




Chuq Von Rospach       -*-      Editor,OtherRealms      -*-      Member SFWA
chuq@apple.com  -*-  CI$: 73317,635  -*-  Delphi: CHUQ  -*-  Applelink: CHUQ
      [This is myself speaking. No company can control my thoughts.]

USENET: N. A self-replicating phage engineered by the phone company to cause
computers to spend large amounts of their owners budget on modem charges.