(This is a long one. It explains how I discovered that something I do almost every day to improve my coding is actually a little ritual that has much in common with practice in the martial arts…)
A week or so ago posted a piece called CodeKata, suggesting that as developers we need to spend more time just practicing: writing throwaway code just to get the experience of writing it. I followed this up with a first exercise, an experiment in supermarket pricing.
This kata arose from some discussions we’ve been having at the DFW Practioners meetings. The problem domain is something seemingly simple: pricing goods at supermarkets.
A binary chop (sometimes called the more prosaic binary search) finds the position of value in a sorted array of values. It achieves some efficiency by halving the number of items under consideration each time it probes the values: in the first pass it determines whether the required value is in the top or the bottom half of the list of values. In the second pass in considers only this half, again dividing it in to two. It stops when it finds the value it is looking for, or when it runs out of array to search. Binary searches are a favorite of CS lecturers.
Rough estimation is a useful talent to possess. As you’re coding away, you may suddenly need to work out approximately how big a data structure will be, or how fast some loop will run. The faster you can do this, the less the coding flow will be disturbed.
Martin Fowler gave me a hard time for Kata02, complaining that it was yet another single-function, academic exercise. Which, or course, it was. So this week let’s mix things up a bit.
Here’s an exercise in three parts to do with real world data. Try hard not to read ahead—do each part in turn.
There are many circumstances where we need to find out if something is a member of a set, and many algorithms for doing it. If the set is small, you can use bitmaps. When they get larger, hashes are a useful technique. But when the sets get big, we start bumping in to limitations. Holding 250,000 words in memory for a spell checker might be too big an overhead if your target environment is a PDA or cell phone. Keeping a list of web-pages visited might be extravagant when you get up to tens of millions of pages. Fortunately, there’s a technique that can help.
Back to non-realistic coding this week (sorry, Martin). Let’s solve some crossword puzzle clues.
The last couple of kata have been programming challenges; let’s move back into mushier, people-oriented stuff this week.
Why do we write code? At one level, we’re trying to solve some particular problem, to add some kind of value to the world. But often there are also secondary objectives: the code has to solve the problem, and it also has to be fast, or easy to maintain, or extend, or whatever. So let’s look at that.