416-993-4953

32 Grenville Street M4Y 1A3

CPRGreaves@gmail.com

Home

Visit www.ChrisGreaves.com for this image!

Best Fit Algorithm (Minimize Wasted Space)

Best-fit is a generalized means of making best use of resources. Best-fit is employed in my best-fit-toolbars macro, that re-arranges your displayed toolbars to make the best use of available space. All of the commands of Best Fit may be accessed directly through the toolbar.

There’s no need to “Turn Off Unnecessary Toolbars”; no need to “Streamline the toolbars you keep”; feel free to go ahead and To add a word-count button, (click Tools > Customize,) or as many buttons as you want. My best-fit-toolbars macro will make the best use of the entire screen.

Installation is a snap - the package is self-installing, and yes, you can inspect the installation code.

That same algorithm can be used to determine the best sequence of transferring your old VCR video tapes to DVD discs.

Free Download .

Introduction

Given a set of lengths (of items) and a buffer length, arrange the items in best-fit manner.

A

B

C

D

E

F

G

H

I

xxxxxx

J

K

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

The output array indicates the relative position of each item.

Item

Row

Column

A

0

0

B

0

1

C

0

2

D

0

3

E

1

0

F

1

1

G

1

2

H

1

3

I

1

4

J

2

0

K

2

1

Example 1: A specific application, e.g. BestFitToolbars takes the result array and uses it to drive a toolbar-button placement process.

Example 2: A specific application, e.g. DVD Movies takes the result array and uses it to assign movies to DVD disks.

Overview

This core algorithm is concerned solely with fitting a vector of length elements into a series of buffers. To that end it is unconcerned with the nature of the items (toolbar menu buttons, Movies for DVDs, music tracks etc.)

The input array is a LONG vector of item lengths. The caller will assemble data describing the items and pass a vector of item lengths to the best-fit procedure. The caller retains ownership of both arrays.

The output is an array of indexes, row and column positions. The index is the pointer to the input array element (and hence for the caller to the original item descriptor array). The row and column positions are zero-origin, as shown in the table in the Introduction.

The working array is the output array, whose row positions are pre-assigned with a negative value. The negative value indicates that the element has not yet been assigned.

The caller receives the output array as a result, and uses the index value to locate the item descriptor in the caller’s original array of data. The row and column values tell the caller where to place the items (our use of “row” and “column” has especial significance when we think of toolbars, but “row” translates to “DVD number” and “column” translates to ‘track within the DVD”.

Method

We pre-process the data by checking that no item length exceeds the given buffer length and returning “failure” if the condition is met. We are NOT going to program around a few items which cannot fit. It is to be expected that ‘best fit” implies that items will fit.

We are processing tangible objects, which are assumed to have a non-zero size. That is, we are not interested in fitting zero-length movies or negative-length rods of steel. Accordingly we drop all non-positive items from the input stream.

The buffer length is supplied by the caller, and we make no fuzzy decisions. If the caller wants to hedge bets by catering for slight deviations in item length, then it is the caller’s responsibility to hedge the best by modifying the supplied value of the buffer.

For example, movies are recorded in minutes, usually three movies to a 6h 5m DVD. The buffer length (in minutes) is 365).

If the movies are sometimes so-many minutes and 2 seconds, or so-many minutes and 58 seconds, the caller may want to say the buffer-length is 363 minutes to tolerate a worst-case scenario of an almost-minute for each of three movies.

We load the input array to the result array, setting all row positions to negative to indicate unassigned.

We loop through the result array looking for unassigned items, and assigning them, one item per loop.

When all items are assigned we are done; the result array is returned as the output array.

During the loop of processing, when we detect the buffer is full, we start a new buffer by resetting the available length and incrementing the row position and zeroing the column position.

The caller receives the result array with elements length, row, column; The length is no further use to us.

The caller must loop through the result array looking for items by row and column, that is, look for all row=0, then look for all row=1, and so on.

Comments

For a dynamic collection such as an accumulating set of audio or visual tracks, the best-fit at any time in the collection will probably not be the best fit as soon as one item is added to the collection.

Generally, we would expect Best Fit to return a smaller set of DVDs (CDs etc) that any previous attempt at organization. Should it not do so, we would like to hear about it.

Next: Case Study 1: The Test Bed Macro


Loading

416-993-4953 CPRGreaves@gmail.com

Toronto, Sunday, May 18, 2014 9:33 AM

Copyright © 1996-2014 Chris Greaves. All Rights Reserved.