Developing Programmers .com

I remember once in a boring lecture about searching and sorting algorithms, somebody I was sitting next to commented that they work in the software industry and that “in the real world, it’s more important to just get the code out the door than to use a fast search algorithm”.

At the time, in my “real world job”, we were having problems with slow sort algorithms holding up the works because the moment a key was pressed the program would look up possible word completions for you… That worked great when there were ten options to choose from. When there were over 30,000 options it made the system unresponsive to simply typing in new data.

The moral of the story? When someone starts a sentence with “In the real world” and then uses absolute words like “always” or “never”, chances are they’re only talking about one very small part of the real world.

Programmers don’t need to memorize hundreds of algorithms. But they should know the algorithms are out there, and have explored enough of them that when a problem comes up they can say “Oh, this is this kind of problem, so that’s where I should look up efficient algorithms for it”.

Having some idea what time complexity means is important when choosing algorithms. Time complexity isn’t about how long an algorithm makes you wait, it’s about how much worse the wait gets when you add more data to process.

“Big O” notation is something anyone with a computer science degree will have been taught. If you got to professional programming via another route and haven’t heard of “Big O” notation then it’s worth doing some reading up on it.

If enough people ask about “Big O” notation then I can write a full tutorial. For now I’ll provide the short, short version: Big O notation describes the shape of the graph that’s made if you plot CPU cycles against number of input data points. The exact numbers don’t matter in Big O notation, just the overall shape the graph makes. An efficient search (for example, “binary search” which halves the possible search space in each iteration) might find its target in log(N) iterations (N being the size of the array being searched). So, searches like this are said to perform in “O(log N) time”.

For large amounts of data, the way the graph asymptotes is far more important than exact numbers. You can double the speed of your CPU, but if your algorithm takes, say, 2^N iterations to complete then the news is bad for large amounts of data no matter how fast your CPU is.

Another reason to become familiar with some basic algorithms is that many of them offer simple tricks that solve otherwise complicated problems. Checking whether a graph is fully connected can be solved quite efficiently, but if you just throw code at it without considering the problem or looking up an algorithm then chances are your code will be inefficient at best.

Wikipedia is a great resource for finding algorithms. A good place to start is their List of algorithms page.

Another valuable resource is the set of libraries available for your language of choice. Most libraries come with (or have available for download) a set of generic algorithms for the most common tasks such as searching, sorting, and complex string matching. It’s worth at least reading the titles of these library functions so you are aware of what’s out there.

Whether you’re sorting a list or finding the least costly way from one point to another in a graph, your first thought should be “is there a good algorithm for this already?” and your second should be “and do I already have a function here that implements it?”.

Sometimes it does pay to re-invent the wheel. Sometimes you can make it better. But if you don’t have time to consider whether your algorithm is particularly good then it pays to know a bit about off-the-shelf algorithms you can use. And, if you do code up something new, why not try generalize it so others can use it too?