16Bit

stuff for programmers

RSS

I was once working on a project with a small group of people.  We had a need to sort some data, a common task in software development.  (So common, in fact, that many languages include a collection of sorting algorithms with their core distribution.)  A co-worker has the assignment to get the data sorted, among other things.  He proceeded to spend the next three days trying to write the code for a quicksort, and never managed to complete it.   For now, let’s ignore the fact that a capable and qualified developer probably ought to be able to write a quicksort well within a single day’s time.

After the three days had passed, he came to ask me for help in completing his code, or at least, the sorting part.  I spent  about ten minutes looking through his code before I just commented it all out and started from scratch.  I implemented a simple bubble sort within a matter of a few minutes, and we had the sorting working in our application, and we were ready to move on.

At this point, he said to me, “I was trying to do a quicksort because it is faster.  A bubble sort is O(n^2), and a quicksort is O(n log n).”  His observation was right.  Bubble sorts are fairly inefficient.  It was just the easiest for me to implement at the time.  So I acknowledged his concern and said, “Let’s try it out and see how the bubble sort works.”  We ran through several test cases, even some of our more complicated data sets, and there was no significant delay in the execution of the application.  Our application only had a need to sort smaller data sets, so having a slower running time was not a big deal.

The moral of the story is don’t optimize until you need to.  Write the code in the simplest, fastest, most obvious way, and optimize when it becomes a problem.  My co-worker spent three days working with a complicated but optimized algorithm, and in the end, it wasn’t needed.  Within just a few minutes, I had put together something that worked well enough for the required uses, and allowed us to move on with the rest of the project.

If you are a little worried that the easy way won’t be optimized enough, just implement it.  It could be that you’ll end up needing to redo it in a more efficient manner, but there’s also a good chance that you won’t ever need to, and you’ll be able to get more accomplished.

In cases like this, it is also to your benefit to design your code in such a way that you can change your mind later.  Put your sorting code in a separate function.  Do what it takes to make it easy to change later.

I guess before wrapping things up I should probably give the normal disclaimer that this is not a hard-and-fast rule, but just a guideline.  There will be times when you already know that you’ll need something more complicated but faster, and you can skip past the easy/naive/brute-force method.  But probably the vast majority of the time, you should at least attempt the simple solution before deciding that the complicated-but-optimized solution is worth spending the extra time on.

View Comments

blog comments powered by Disqus