четверг, 16 февраля 2017 г.

Search Algortihms in the Real World

In the middle of my university life I had a very strong desire to build a computer game. I was studying for a software engineer and still understood little about most of the software applications. At the same time I loved PC games, which clearly brought me to the idea that I should produce one - the one with the best gameplay, of course. Many of the guys with the same background had that wish and like most of them I didn't succeed.

I spent a fair portion of my free time thinking over the game's design, writing the explanations in a textbook and studying computer graphics. The problem is that in these activities I focused on the things that were easier to comprehend for me. I liked to think through game mechanics - for example the way damage is dealt to the player. I worked this question out on a very detailed level - in many cases descending to the names of C++ classes and of course laying out the calculation rules. With graphics, I focused on trying to make primitives move around the screen using OpenGL, because moving stuff looked like an essential part of game development. This all happened where neither setting, nor even key game features were defined - I hardly settled with the genre. Instead of looking at these high-level concepts of the game, I grasped the details, which I could easily stick into my head, without even understanding what are the key building blocks that I will have to construct a video game from. Speaking in algorithms language, I was doing a depth-first search not wishing too see the entire tree that I will have to traverse eventually.

Recent observations at interviews and during the normal work process brought me to the idea that such a mistake is common among many younger developers. When put in front of an unfamiliar problem they tend to catch some detail that they understand and pursue it to the deep. Because they don't take time to step back and take a look at the problem as a whole, they may end up with weak solutions suffering from various illnesses that happen in the software world. Most likely you will see multiple leaky abstractions and dozens of lines of ad-hoc code in the programs produced this way. And of course don't be too optimistic about finding there clearly separated layers, constituted of the objects that comply with Single-Responsibility Principle.

After acquiring reasonable development experience we tend to replace the depth-first strategy with the breadth-first search. This happens not only because older developers are slower beasts, but more due to the acknowledgement of importance of the full context for the correct solution to the problem. The mistakes committed earlier make us approach both high- and low-level decisions with great respect to the surroundings and see the drawbacks of diving into details before thinking of the solution as a whole.

This obviously makes a lot of sense when we speak of software design and architecture definition, but actually the same breadth-first strategy is applicable to such activities as coding and bugfixing. For example, when analyzing a bug it is tempting to follow the first breadcrumbs seen in the data in an attempt to understand the issue, but this way one may end ep trying every possible hint and spend hours exploring dead-ends. Alternatively, one may take time to fully understand the context of the issue, appreciate its complexity and collect as many facts as possible before even trying to make assumptions regarding the cause of the problem. In this case he will be able to see clearly which guesses are worth a deep investigation and which can be ignored altogether.

There is a similar situation with, for example, writing blog entries. For some people it is natural to produce a good article  simply by letting their thoughts flow onto paper. For others producing a reasonable piece of writing requires planning it and doing a couple drafts first. I don't belong to the first kind and going the depth-first way always results in frustration and wasting lots of my time on a couple short paragraphs. To be honest, sometimes its very hard for me even to produce the first draft from the start to the end - details kill me on the way. Instead, I begin with a rough outline consisting of several key points, then gradually add several sub-points to each of them. Only after this two-tier plan is there, I would start expanding the sub-points to rough sentences, which make a foundation for the draft. This looks very much like traversing the tree of the future blog post with the breadth-first search algorithm, except for the fact that here nodes and leafs are themselves created by the search process.

While I have enough development and writing experience to understand these things, sometimes I still find myself using the details-first approach where breadth-first search is more appropriate. To some extent, this happens because there is always eagerness to produce results and the depth-first path always seems short and clear - until you start going. But at the same time, it may be the case that in absence of the right words to distinguish the two strategies nothing forced me to make a conscious choice - the analogy with the search algorithms came to me only recently. In addition to making the choice clearly visible, it also brings the criteria for picking one of the two approaches. When you need to devise a good solution or just to understand a large and potentially complex problem, breadth-first search will work better - the theory says it guarantees the best result possible. If, however, you need the result early and don't care about its quality too much - for example when building a quick prototype to get an idea of the look and feel of a future product - you'd better use the depth-first search, as it usually yields faster. Sounds obvious, but somehow just having this analogy with the algorithms world in mind seems to make the task of selecting the right approach to any problem easier.