Java Reference
In-Depth Information
deal with variations of this problem. Most such implementations involve
the following tuning step. Directly testing whether a given complex ob-
ject contains the point in question is relatively expensive. Instead, we can
screen for whether the point is contained within a bounding box for the
object. The bounding box is simply the smallest rectangle (usually defined
to have sides perpendicular to the x and y axes) that contains the object.
If the point is not in the bounding box, then it cannot be in the object. If
the point is in the bounding box, only then would we conduct the full com-
parison of the object versus the point. Note that if the point is outside the
bounding box, we saved time because the bounding box test is cheaper than
the comparison of the full object versus the point. But if the point is inside
the bounding box, then that test is redundant because we still have to com-
pare the point against the object. Typically the amount of work avoided by
making this test is greater than the cost of making the test on every object.
Example3.20
Section 7.2.3 presents a sorting algorithm named Selec-
tion Sort. The chief distinguishing characteristic of this algorithm is that
it requires relatively few swaps of records stored in the array to be sorted.
However, it sometimes performs an unnecessary swap operation where it
tries to swap a record with itself. This work could be avoided by testing
whether the two indices being swapped are the same. However, this event
does not occurr often. Because the cost of the test is high enough compared
to the work saved when the test is successful, adding the test typically will
slow down the program rather than speed it up.
Be careful not to use tricks that make the program unreadable. Most code tun-
ing is simply cleaning up a carelessly written program, not taking a clear program
and adding tricks. In particular, you should develop an appreciation for the capa-
bilities of modern compilers to make extremely good optimizations of expressions.
“Optimization of expressions” here means a rearrangement of arithmetic or logical
expressions to run more efficiently. Be careful not to damage the compiler's ability
to do such optimizations for you in an effort to optimize the expression yourself.
Always check that your “optimizations” really do improve the program by running
the program before and after the change on a suitable benchmark set of input. Many
times I have been wrong about the positive effects of code tuning in my own pro-
grams. Most often I am wrong when I try to optimize an expression. It is hard to
do better than the compiler.
The greatest time and space improvements come from a better data structure or
algorithm. The final thought for this section is
First tune the algorithm, then tune the code.
