
|
 |
|
Michael Abrash's Graphics Programming Black Book, Special Edition
by Michael Abrash
The Coriolis Group
ISBN: 1576101746 Pub Date: 07/01/97
|
Chapter 10 Patient Coding, Faster Code
How Working Quickly Can Bring Execution to a Crawl
My grandfather does The New York Times crossword puzzle every Sunday. In ink. With nary a blemish.
The relevance of which will become apparent in a trice.
What my grandfather is, is a pattern matcher par excellence. Youre a pattern matcher, too. So am I. We cant help it; it comes with the territory. Try focusing on text and not reading it. Cant do it. Can you hear the voice of someone you know and not recognize it? I cant. And how in the Nine Billion Names of God is it that were capable of instantly recognizing one face out of the thousands weve seen in our lifetimeseven years later, from a different angle and in different light? Although we take them for granted, our pattern-matching capabilities are surely a miracle on the order of loaves and fishes.
By pattern matching, I mean more than just recognition, though. I mean that we are generally able to take complex and often seemingly woefully inadequate data, instantaneously match it in an incredibly flexible way to our past experience, extrapolate, and reach amazing conclusions, something that computers can scarcely do at all. Crossword puzzles are an excellent example; given a couple of letters and a cryptic clue, were somehow able to come up with one out of several hundred thousand words that we know. Try writing a program to do that! Whats more, we dont process data in the serial brute-force way that computers do. Solutions tend to be virtually instantaneous or not at all; none of those N log N or N2 execution times for us.
It goes without saying that pattern matching is good; more than that, its a large part of what we are, and, generally, the faster we are at it, the better. Not always, though. Sometimes insufficient information really is insufficient, and, in our haste to get the heady rush of coming up with a solution, incorrect or less-than-optimal conclusions are reached, as anyone who has ever done the Times Sunday crossword will attest. Still, my grandfather does that puzzle every Sunday in ink. Whats his secret? Patience and discipline. He never fills a word in until hes confirmed it in his head via intersecting words, no matter how strong the urge may be to put something down where he can see it and feel like hes getting somewhere.
Theres a surprisingly close parallel to programming here. Programming is certainly a sort of pattern matching in the sense Ive described above, and, as with crossword puzzles, following your programming instincts too quickly can be a liability. For many programmers, myself included, theres a strong urge to find a workable approach to a particular problem and start coding it right now, what some people call hacking a program. Going with the first thing your programming pattern matcher comes up with can be a lot of fun; theres instant gratification and a feeling of unbounded creativity. Personally, Ive always hungered to get results from my work as soon as possible; I gravitated toward graphics for its instant and very visible gratification. Over time, however, Ive learned patience.
 | Ive come to spend an increasingly large portion of my time choosing algorithms, designing, and simply giving my mind quiet time in which to work on problems and come up with non-obvious approaches before coding; and Ive found that the extra time up front more than pays for itself in both decreased coding time and superior programs.
|
In this chapter, Im going to walk you through a simple but illustrative case history that nicely points up the wisdom of delaying gratification when faced with programming problems, so that your mind has time to chew on the problems from other angles. The alternative solutions you find by doing this may seem obvious, once youve come up with them. They may not even differ greatly from your initial solutions. Often, however, they will be much betterand youll never even have the chance to decide whether theyre better or not if you take the first thing that comes into your head and run with it.
The Case for Delayed Gratification
Once upon a time, I set out to read Algorithms, by Robert Sedgewick (Addison-Wesley), which turned out to be a wonderful, stimulating, and most useful book, one that I recommend highly. My story, however, involves only what happened in the first 12 pages, for it was in those pages that Sedgewick discussed Euclids algorithm.
Euclids algorithm (discovered by Euclid, of Euclidean geometry fame, a very long time ago, way back when computers still used core memory) is a straightforward algorithm that solves one of the simplest problems imaginable: finding the greatest common integer divisor (GCD) of two positive integers. Sedgewick points out that this is useful for reducing a fraction to its lowest terms. Im sure its useful for other things, as well, although none spring to mind. (A long time ago, I wrote an article about optimizing a bit of code that wasnt even vaguely time-critical, and got swamped with letters telling me so. I knew it wasnt time-critical; it was just a good example. So for now, close your eyes and imagine that finding the GCD is not only necessary but must also be done as quickly as possible, because its perfect for the point I want to make here and now. Okay?)
The problem at hand, then, is simply this: Find the largest integer value that evenly divides two arbitrary positive integers. Thats all there is to it. So warm up your pattern matchers...and go!
The Brute-Force Syndrome
I have a funny feeling that youd already figured out how to find the GCD before I even said go. Thats what I did when reading Algorithms; before I read another word, I had to figure it out for myself. Programmers are like that; give them a problem and their eyes immediately glaze over as they try to solve it before youve even shut your mouth. That sort of instant response can certainly be impressive, but it can backfire, too, as it did in my case.
You see, I fell victim to a common programming pitfall, the brute-force syndrome. The basis of this syndrome is that there are many problems that have obvious, brute-force solutionswith one small drawback. The drawback is that if you were to try to apply a brute-force solution by handthat is, work a single problem out with pencil and paper or a calculatorit would generally require that you have the patience and discipline to work on the problem for approximately seven hundred years, not counting eating and sleeping, in order to get an answer. Finding all the prime numbers less than 1,000,000 is a good example; just divide each number up to 1,000,000 by every lesser number, and see whats left standing. For most of the history of humankind, people were forced to think of cleverer solutions, such as the Sieve of Eratosthenes (wed have been in big trouble if the ancient Greeks had had computers), mainly because after about five minutes of brute force-type work, peoples attention gets diverted to other important matters, such as how far a paper airplane will fly from a second-story window.
|