Engineers think in terms of tradeoffs. For every new feature added, something is taken away, or made more complicated. An abstraction that whisks away complexities oft brings its own complexity. Entertain the question “What aren’t you telling me?” at your next vendor meeting.
But, sometimes, assuming you have to make an engineering tradeoff to make some improvement can actually block you from thinking through to an genuinely elegant solution, one simply superior in all ways.
This is one of the pearls of wisdom Jon Bentley proffered in book “Programming Pearls.” That’s pearls, not Perl. Bentley wrote this book before Larry Wall created Perl, in 1986, while Bentley was at AT&T Bell Laboratories.
In the first chapter, Bentley examines the received wisdom of programmers have about engineering trade-offs concerning speed and resources: The amount of memory that a program uses can be reduced, assuming one doesn’t mind the program taking longer to complete, the thinking goes.
This isn’t always the case, however. “It has been my experience more frequently, though, that reducing a program’s space requirement also reduces its run-time,” Bentley wrote. “Less data to process means less time to process it.”
Coming up with such a solution, though, requires more thought, Bentley warned. Sometimes it takes an “aha” moment, in which the developer arrives at an unexpectedly simple solution for a seemingly difficult problem. As an example, Bentley presented the problem of finding a single missing integer in a long string of sequential integers.
One could have the computer do a sequential search, going through the list two numbers at a time, checking to see if they are. This approach can take a long time, however, an average of n/2 comparison for “n” number of integers. The genius of another technique, called binary search, is that it simply counts the number of digits in the set, then cuts the set by halves until the missing digit is pinpointed. This approach cuts the workload by an order of magnitude and is faster as well.
“Careful analysis of a small problem can sometimes yield tremendous results,” he wrote.
Feature Image: Sticker in a NYC subway station, midtown Manhattan.