Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Using bounds for optimization

May 27, 2009

An optimization technique occurred to me recently that I realized that I've seen many times, but rarely if ever have I seen it described clearly.  This note is an attempt to fix that.

Suppose you want to find the smallest element in an array.  Unless the array is sorted, you can't do better than to inspect each element and remember which one is the smallest you've seen so far.

Now let's complicate the problem a bit: You have a two-dimensional array of unsigned integers, and you want to find the row with the smallest sum.  Of course, you can use a similar approach, by computing the sum of the elements in each row and remembering which row is the smallest you've seen so far.  However, you can usually make the program significantly faster by realizing that as you compute the sum of each row's elements, you can stop as soon as the sum exceeds the smallest you've seen so far.

The general form of this technique is that if we can put constraints on the result we are willing to accept from a computation, then as soon as we know that the result cannot fit those constraints, we can reject it without doing any more work.

As another example, consider a program that knows where all the gas stations are on a map, and tries to find the one with the smallest driving distance from a given point.  In general, it may be hard to compute the driving distance between two points--but we do know that the driving distance can never be less than the direct distance--that is, the length of a straight line between the two points.

Therefore, as we look at gas stations, we can start by computing the direct distance; if that distance is greater than the shortest driving distance we have found so far, we do not need to compute the driving distance to the current gas station because we know it cannot be the smallest.

Character-string implementations sometimes use a related technique to implement comparisons.  If comparison is defined so that strings of different lengths are never equal, then an equality comparison should probably begin with a length comparison.  Doing this comparison first not only avoids much expensive computation in the case that the strings have different lengths, but also makes the rest of the comparison easier because of the knowledge that it is done only when the lengths are the same.

Finally, it may be worth noting that a similar optimization is widely used in game-playing programs, where it is called alpha-beta pruning.  The idea is that is you are evaluating a move X that you might make, you do not need to consider all of your opponent's responses; once you have found a response that is better (for your opponent) than the opponent's best response to a different move Y you might have made, you don't need to think about X any further, because you are always better off with move Y.

As the computations become more complicated, the value of this kind of optimization becomes clearer.  Therefore, the place to look for applications is where it is less clear--in moderately complicated computations--because it is there that you are mostly likely to overlook the opportunities.

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.