pattern matching

"I have 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 I've found that the extra time up front more than pays for itself in both decreased coding time and superior programs."

Pattern Matching

Extract from Chapter 10,
Graphics Programming Black Book,
By Mike Abrash

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. You are a pattern matcher too and so am I. We can't help it; it comes with the territory. Try focusing on the text and not reading it. Can't do it. Can you hear the voice of someone you know and not recognize it? I can't. And how in the Nine Billion Names of God is that we are capable of instantly recognizing one face out of the thousands we have seen in our lifetimes - even years later, from a different angle in a 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, we are somehow able to come up with one out of several hundred thousand words that we know. Try writing a program to do that! What's more is that we do not 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 "N ^ 2" execution time for us.

It goes without saying that pattern matching is good; more than that, it’s a large part of what we are, and, generally the faster we are at it, the better. Not always though. Sometime 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 Time Sunday crossword will attest. Still my Grandfather does that puzzle every Sunday and in Ink. What's his secret? Patience and Discipline. He never fills a word in until he's 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 he's getting somewhere.

There is surprisingly close parallel to programming here. Programming is certainly a sort of pattern matching in the sense I've described above, and as with crossword puzzles, following your programming instincts too quickly can be a liability. For many programmers, myself included, there is a strong urge to find workable approach to a particular problem and start coding it right now, what some people call "hacking" a program. Going with the first thing that your programming pattern matcher comes up with can be a lot of fun; there's instant gratification and a feeling of unbounded creativity. Personally I have always hungered to get results from my work as soon as possible; I gravitated towards graphics for its instant and very visible gratification. Over time, however, I've learned patience.

In this chapter I am going to walk you through a simple but illustrative case history that nicely puts 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 you have come up with them. They may not even differ greatly from your initial solutions. Often, however they will be much better - and you will never even have the chance to decide whether they are better or not if you take the first thing that comes into your head and run with it.

...