Grant Edwards wrote:
On 2007-04-12, Grant Edwards <[email protected]> wrote:
I've been thinking more about the problem. I think with the
degenerate case of only 2 bins, the problem isn't actually that
hard. If I've got it figured correctly, doing it optimally is
O(N^B), where N is the number of input sections and B is the
numbr of bins. With N==2, a brute force optimal solution
should be feasible (especially for a small number of input
sections).
That can't be right. It's a combinatorial problem, so it has
to be O(N!). In any case, for large N the size of the chunks
that you're packing will be small, and any of the standard
non-combinatorial heuristic algorithms should work fine.
The brute force optimal algorithm would be O(B^N), not O(N^B), and I
can't see an O(N!) solution (not that you'd want one - it would be worse
than O(B^N)). For each input section, you have a choice of B bins to
put it in - thus there are B^N combinations to try to find which is the
"best".
Fortunately in the case of linking, there is a very simple fitness
function - if the link fits in the available memory, it is of fitness
"1", if it fails, it is fitness "0". So any combination that packs the
input sections into the available memory is optimal. The simple first
come, first served algorithm will therefore give an optimal solution in
almost all cases. If it modified to placing the input sections
according to length (longest first) and putting them in the smallest
possible free space, you have an algorithm that will be fast and which
will cover any realistic case (although theoretically you might still
have to check B^N cases in the worst case for a truly optimal solution).
Of course, if it is shorter and faster to call functions that are at
nearby addresses rather than using full 20-bit absolute addresses, then
you can think of far more complex algorithms in an attempt to get
optimal solutions. That would involve changes to the generated object
code too (20-bit calls could be reduced to shorter relative ones). That
might be an nice project for a Googol "summer of code" project.
