Disk balancer, best fit; too expensive?

Reply to topic
9 posts
I want to write code that balances certain files in a best fit manner. So if I have 40GBs more free space on drive E: than drive D :, it'll move a 19GB file to drive E: from D : rather than two 8GB files, or in another case, two 9GB files will be moved, rather than a 15GB file. I'm kind of at a loss at how to proceed but before I get heavily invested, rewriting functions I find on the web into C# or powershell, would this be too expensive for usual file amounts? I imagine the possibilities will explode and it'll run dog slow for say 20,000 - 100,000 files or can a modern Core i7 handle that much assuming it requires something like checking every possible combination that will fit?
Knapsack problem.
As Blacken00100 is alluding to, this problem is very hard to solve exactly. But before we get to that issue, there are some other questions, like "why the heck would you want to do this?"

I am doubtful that this approach is a good solution to any real-world problem. If you have a real-world problem, I suggest that you tell us what it is. Then we might be able to suggest a solution that doesn't require the knapsack problem. If you do need to solve it this way, there are some approximate solutions that get you pretty close to the optimal solution, outlined on the Wikipedia page.

Alternatively, the greedy method of "copy the files is descending order of size until I stop balancing, starting at size_differential/2" would probably work pretty well, and has the advantage of achieving the best transfer speed on real hardware. But again, I'm skeptical that there's a good reason to do this in the first place.
Nah, it's not a real world problem. I just get tired of copying files from one drive on my personal system to the next drive when I run out of space on one because I carelessly put too many files on the one drive; so I figured I'd put some kind of balancer code in my nightly robocopy task scheduled powershell script. I considered the simple solution, of just copying the smallest file over, until the next smallest file would surpass size_differential/2, but I thought it'd be neat to have an exact solution. Since the files in question are in libraries, it doesn't matter what disk they are on.
If you really don't care what file is on what disk, the simpler solution would be to treat them as a single volume using JBOD or something similar.
Or storage spaces in Win8/Server12
I don't care for raid/jbod/storage space for various reasons, won't go into it. Anyway, I came up with something. But as I suspected it's dog slow, I ran it on 14,000 files looking for the best fit for 10 bytes and it ran for 20 minutes before I stopped it. I only really want it for my movie directories, which are only ~160 files so it's a workable solution there, but for general use it will not do. I'm not 100% sure it works right, but I took 3 movies, added their sizes, and put that in as the size differential, and it returned those 3 movies, so I'd say that's close enough. I'll post the code here in case anyone is curious, it's in PowerShell:

function getBestFiles{

   param([long]$diff, [system.array]$files,[int]$i)   

   $return = @{}
   $return.bestfiles = @()
   $return.diffdiff = $diff

   for (; $i -lt $files.count; $i++)
      if (($diff - $files[$i].length) -ge 0)
         $newreturn = @{}
         $newreturn = (getBestFiles ($diff-$files[$i].length) $files ($i+1))
         if ($return.diffdiff -gt $newreturn.diffdiff)
            write-host "$($files[$i].fullname) Size: $($files[$i].length)" # debug message, delete-able.
      else {break}   
   return $return   

# stub below to demonstrate usage.

   $files = @(dir d:\ -recurse -ea 0|?{$_.psiscontainer -eq $false})|sort length
   $diff = 10
   getBestFiles $diff $files 0

aggressiva wrote:
Are you willing to move lots of files around when you add your 161st movie? This can happen if you always look for the optimal solution.
aggressiva wrote:
Nah, it's not a real world problem.

I for one support learning stuff by unnecessarily solving tough problems while screwing around. It's one of the best ways to learn.

I did a (very) quick scan through your code and am pretty sure its one of two problems:
  1. I didn't see any allowable tolerances. Constant optimization is insanely expensive. To avoid this, most algorithms allow some small amount of sub-optimal state before launching another round of optimization.
  2. Double check that you aren't re-querying the file list unnecessarily. Recursively searching directories is slow and expensive. Test this by outputing a debugging line every time you do any file access outside of copying files. If you see that debugging line numerous times, you've just spotted one of the issues.

(NOTE: I intentionally didn't go back and confirm/rule out either of the above. If you like learning stuff in your spare time like I do, you'll have more fun check both of the above for validity yourself.)
9 posts