Author: Stan Eisenstat
Subject: Why is my Binpack so slow?
Date: Tuesday, 11 Feb 2020, 14:24:04

The test script terminates each test if it runs for
more than 2 seconds (Hwk2/Binpack takes less than
1/4 second), and prints a "Killed" message to the
standard error.

If your Binpack might fails a backtracking test in
this manner, try running the test as follows:

  % /bin/time /c/cs223/Hwk2/Tests/t11

letting it run for at least 15 seconds.

If you have to use CTRL-C to terminate the test, it
is likely that you have not implemented one of the
backtracking heuristics correctly.  The description
of the test specifies which (if any) heuristics it
requires.

But if it finishes in between 2 and 15 seconds, the
problem is likely to be the time your code spends
trying to place each item (excluding the time spent
in recursive calls).  That time should be proportional
to the square of the number of bins in use and should
not depend on the number of items.  This follows from
the general form of backtracking:

  for each bin where the next item can be placed (including one empty bin)
  ...
  return the minimum number of bins found by any of the recursive calls

where the outer loop runs #bins + 1 times, not #items
times; and from the cost of implementing Heuristic D
(which should be constant since the items are sorted
in decreasing order) and Heuristic E (which should be
proportional to the number of bins in use).

--Stan-