Algorithms Don’t End Here

2013-12-16 15:07

There is a particular way many programmers tend to think about “algorithms”. I put the word in quotes because it’s a really just a small subset of actual algorithms that they refer to by this term.

In short, “algorithms” are perceived as self-contained boxes, classic procedures that take data in and spit results out. They are blocks, or packages, stowed in a corner of some bigger program, coming out only to perform they designated function. Clearly separated from the “usual” code, they may even occur only as libraries, both standard language libraries or third party extensions.
What’s important is being out of sight, out of mind. You are not supposed to delve into them. You can use them, or add new ones – sometimes even implementing them yourself! – but once you’re done, you get back to “real” code. Normal code, typical code, usual code; code that doesn’t have those “algorithms”.

Amusing as it is, this mode of thinking may actually be spurred by reading works such as the classic Introduction to Algorithms by Cormen et al. Since the subject is intrinsically quite heavy and full of intricate theory and math, it’s very tempting to skirt its surface. Sure, you need to know about most of the important algorithms, but you don’t really have to know them. It’s perfectly acceptable to skip the details of their implementation.
And why not? You can always go back and look it all up! Most of the important stuff is already implemented anyway. When was the last time you had to roll out your own sort() function?… Great programmers reuse, haven’t you heard? We should all stand on the shoulders of giants!

Well, that’s lovely. But I’ve got some bad news. There are no “algorithms”. You cannot compartmentalize programs to have demarcated “difficult” parts. You can try, of course, but it’s futile. They won’t comply, because the pesky reality itself will inevitably tear down any walls you choose to surround the “algorithms” with.

Let’s say you have your isolated, tricky procedure. Over the lifetime of a program that contains it, any of the following is very likely to happen:

  • The input data becomes too large to be stored completely in memory. At least some operations will need to be performed at a smaller portion, and then results will have to be merged.
  • Waiting for complete input becomes unfeasible. You are now required to compute the result incrementally (or online, to use the traditional term), adjusting it every time a new chunk of information comes in.
  • While computational complexity of the algorithm is still acceptable, practical factors mandate limiting of e.g. disk reads or network requests. The procedure needs to be reworked to incorporate additional caching, or pre-computation, or preliminary analysis of input, or obtaining more data outside of main logic, or…
  • User studies indicate a growing level of discontent about the lack of UI feedback when performing the Complex and Time-consuming Task™. To alleviate this, the code must now report at least approximate completion progress, so that the interface can be made more responsive by adding a certain widget.
  • In an attempt to improve throughput, the application has switched to using asynchronous I/O. As a result, the algorithm must be split into several callbacks and state has to be somehow passed between them. (Extra credit if the programming language has no support, or poor support, for closures).

Many, many other situations could be added to this list, but the point should nevertheless be clear. It doesn’t matter how tightly you’re going to shut the tricky procedure off the rest of the code, the ongoing evolution of the latter will eventually effect changes on it. After a while, you won’t be dealing with a single algorithm, but a whole subsystem with multiple tendrils touching other parts of your program.

At this point, you can’t pretend it can be confined to a dark, forgotten place anymore. Now it has to be taken into account when dealing with the “normal” code on daily basis.
And it’s nothing to fear of, because it simply is just a normal code.

Tags:
Author: Xion, posted under Computer Science & IT »



Adding comments is disabled.

Comments are disabled.
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.