Optimal Optimisation

I don't write optimised code. Generally speaking, the computer is fast enough that worrying about how often I create a new string object is absurd. Code readability and extensibility is what matters to me.

Every so often, I have a process I want to speed up. So it was in looking at the Flipping Coins problem : http://cplus.about.com/od/programmingchallenges/a/challenge31.htm. I had a brute force method that was taking 30 seconds to solve a five by five grid, and a lot longer to decide there was no solution.

I'm accustomed to colleagues saying they can speed code up by looking for inefficiencies at the code level. Pre-allocate the storage of a StringBuilder class they say, that sort of thing. I'm always saying that we can have a greater effect on by writing a better algorithm - doing the same thing in fewer steps.

So I decided to test my position. I could see that I could make the brute force more efficient by using recursion - I would create fewer objects on the way to finding the solution. So I implemented that, creating code that was very clever and therefore very difficult to read. Result : five times speed increase.

Then I thought hard about how to solve these problems, came up with a new technique. Coding that was easy - none of this tricky recursion. Speed improvement : more than a thousand times faster than the 'optimised' recursive version, five thousand times faster than the brute force version.

I'm convinced!

Brute force method : 30 seconds
Some code optimisation : 6 seconds
Algorithmic change : 1/200 of a second