From algorithm to data structure

"It seems that with examples of sorting you can build a whole course of programming."
Niklaus Wirth

“I'm afraid I can't explain all this to you,” said Alice politely. “I myself don’t understand anything. So many transformations in one day can be confusing to anyone.”
Lewis Carroll

The formulation of the problem, as a rule, leaves the programmer the opportunity to choose a path for solving it. Evidence of this is a variety of algorithmic mechanisms, including not only those mentioned above, but also some others. Are there any doubts that they should belong to the programmer’s arsenal?

In fact, a program written outright may well be ineffective. But does every programmer bother to find out? Unfortunately, we repeatedly had to deal with typical examples of “hidden” inefficiency when discussing algorithmic and software solutions with young coders. The most popular arguments are that the finished program, firstly, works, secondly, it works quickly, and in general, they say, “what do you want from me (or from it, I mean, programs)”.

Indeed, the presented product looks workable, and it is difficult to convince the encoder that he should think more. The fact is that the level of complexity of learning tasks that novice programmers have to deal with is not very high. If you have to build an algorithm of polynomial complexity, then it usually does not exceed O (n ² ) , in extreme cases, O (n ³ ) . And we already know that with small values ​​of n, the real time of the execution of such a computational process does not give reason to search for a better solution. At the same time, the preparation of any significant data set, in order to check the behavior of the program with large n , the same programmers do not bother themselves. As for the complexity of the exponential, then such tasks in the curriculum - we mean an ordinary school course of computer science - are quite few, if they are presented at all.

So, we will proceed from the need to include in the "gentleman's set" of the programmer as many basic algorithms as possible. Saying “as much as possible”, we do not plan to simply renumber them, and then, in order of priority, discuss them. Nevertheless, it is advisable to carry out some of their classification.

With one of the options for such a classification, you had to face at an early stage of acquaintance with the discipline of programming. There is a view of the classification of software mechanisms by types that precede the algorithmic - linear algorithm , branching and loop .

Of course, the discussion of efficiency only begins with the advent of cyclic processing. And we need to go further. Tempting idea Wirth, rendered in the epigraph. But the goal that we pursue in this section is much more modest: we do not aim at the "whole" course, we just want to demonstrate the differences in the algorithmic content of the tasks that arise before the programmer. What prevents us from doing something similar — or at least trying — based on an object familiar to any reader — the multiplication table !? So, we propose to treat the further reasoning as a kind of detailed exercise in the design of algorithms.

Naturally, before turning to the table, you should set the task. Let’s accept the following wording: “ calculate the corresponding output value — their product” from the input values ​​of a pair of natural numbers. On the keyword "calculate" note: its presence is reflected in how the following is built

Such an explanation, or something of the same kind, describes an algorithm for multiplying two factors — first by second — in the class of natural numbers . The complexity of this algorithm is O (n) , where n is the second factor.

Algorithm 2. Multiplication 2

A few more problems will be caused by the situation of a large number of heaps (even if in the new example there are 26 of them) and matches in them (15 each). Now it is appropriate to recall the multiplication algorithm "in a column . " Fig. 2 Multiplying here 6 by 15, in the course of the calculations we must multiply 6 by 5 (or 5 by 6), which allows us to reduce many steps of the A4-2 algorithm to the calls of Algorithm 1. We can assume that at one time this version of the algorithm was one of the first reader's experiences in applying the method of reducing the task to subtasks.

Such a search is not a primitive operation. It requires cyclic processing of candidates in a certain sequence - in our case, enumeration and verification of rows 1 through 5, then columns 1 through 6. It is easy to see that the order of candidates in the sequence can be set differently: for example, from the bottom line - upwards and, then, from the rightmost column - to the left. But the nature of these differences is only technical, they do not affect the assessment of the complexity of the search for the elements in the sequence.

We are, of course, interested in the algorithmic difference. In principle , the divide-and-rule method works differently, although here we only mention it, leaving the discussion of the mechanism for the future.

Thus, in our classification, it is necessary to provide a place not for a unique mechanism — a sequential search , but for a whole family of search algorithms , in which, by the way, there are other representatives besides the two already mentioned. So the table search technology - in this case - is split into two independent subtasks of the search in a linear array .

Let us return once more to the initial formulation of the problem. It turns out that we changed it "imperceptibly" as soon as the table appeared. In fact, modification of the wording is associated with the replacement of the keyword "calculate" with the word "find" . That is, the corresponding formulation of the problem, as soon as it was supplemented with a suitable data structure , immediately suggested to us another algorithmic solution. We will discuss the data structures below, but for now we will try to develop this consideration further.

Essentially, the statement of the problem and familiarity with Algorithm 3 dictated the choice of structure, and the input data determined the values ​​of the parameters of the structure.

Of course, not every algorithmic decision is worth making, - but we are only reasoning for now, and have not rushed to write the program code right away. And here a simple argument shows that Algorithm 4 is unlikely to suit us. Indeed, with an increase in the number of rows m and columns n - that is, the values ​​of input parameters - the size of the table should be no less than the product of the specified values. We have to recall the capacitive complexity of the algorithm, which is associated with the storage of information in the selected data structure, and will be O (m · n) .

Arguing further, we note that problems arise with temporal complexity. It is not enough to allocate memory for the structure; to store data, you first need to place them there, and this will also take time on the order of O (m · n) . By the way, the initial placement of data in the selected structure is often called its initialization . So, with a single calculation of the 15 × 26 product, the latter algorithm does not suit us at once for two reasons: due to the inefficiency of the time spent at the initialization stage and because of the capacitive non-effectiveness of the selected structure.

Naturally, the same reasoning is relevant for any pair of values ​​of the factors. How to be: after all, the problem of multiplying natural numbers has to be solved regularly? In non- computer practice (microcalculators - not counted), we often use two alternative algorithms, switching at the right moments. The mechanism is to multiply numbers with a bit more than 1 in a column, according to Algorithm 2, and for bitwise operations, refer to the multiplication table of Algorithm 3. With this approach, stored in the mind - but initialized in childhood! - the multiplication table has the usual sizes 10 × 10 (or 9 × 9), and it does not reach Algorithm 4.

However, the size of the table 10 × 10 light wedge did not converge. The reader is probably curious to know that Australian schoolchildren are "cramming" a table of 13 × 13. So, and there is a place for choice. Well, and at computer processing when the binary numeral system is used , the table becomes absolutely small - 2 × 2. Does it make sense to initialize it in RAM, or use other algorithms, we will discuss in Chapter B, where we will talk about computer arithmetic .

However, we will not be distracted. I hope the reader has not forgotten that our goal is to outline the range of tasks and algorithms encountered in programming practice and, of course, in our course. And the multiplication table serves us as “only” a model object. But in our classification is added another method for solving problems - this is computer simulation . More precisely, numerical simulation , in which a computer serves as a high-speed performer and a demonstrator of processing results. We do not intend to deeply intrude into this independent field of computer science, we confine ourselves to just one example. We mean the visualizers of algorithms , which are many in our course. In fact, these are just models, and their application for the realization — in full — of the possibilities and goals of the corresponding algorithms is by no means envisaged.

Let us now note that in the considered algorithms we take into account, albeit sometimes implicitly, but when encoding, of course, explicitly, the form of presenting information . So, speaking of data, we everywhere typified them somehow, for example, in Algorithm 1, referring to natural numbers. What can we say about machine arithmetic, where form, to a large extent, dictates processing algorithms.

We also used the term “structure” to present the data, without specifying the content, since the reader came across this concept in a programming language. In the algorithms, data structures are understood somewhat more broadly than in a specific programming language, but the general characteristics of the concepts are the same. In any case, there is a finite set of elements related — within the structure — by a certain order . The established order makes it possible to distinguish the elements of the structure by location in it or relative to each other .

A programming language may or may not allow the manipulation of the entire structure as a whole, but it always allows the processing of its constituent elements separately. Both possibilities are relevant in algorithms. Each processed structure is assigned its own set of operations , and in this sense, the capabilities of the language are usually already. Thus, individual algorithmic operations often have to be emulated by a sequence of operations allowed by the framework of the language. In detail, these questions are also waiting to be discussed, - we will proceed to it, starting with Chapter D.

In this sense, when processing the multiplication table, the operations are allowed - and, accordingly, the mechanisms of their implementation are regulated - direct access to a row or column by a given number, writing the value of a table element during its initialization, reading the element.

Finally (and perhaps this should have been started), combining the elements into a structure requires that they have a certain - at least one - common property. In our model problem, this attribute is the belonging of elements to the class of natural numbers.

Imagine that, in addition to the digital value, the cells of the multiplication table also placed its verbal notation, for example, "30, thirty". This option could be useful to us, say, as a methodological guide for teaching the numeral English. Then the value of the structure element is the entire record "30, thirty", the key of the record is "30", and the information part - "thirty" - is accessible by key .

For the chosen representation of the concept, the key and the number (or index ) of the element are not interchangeable. The key assignment is in the identification of the structure element, the index assignment is to provide access to the element. So, in the table in fig. A4-3 keys are present in an explicit form: the row keys are located in the left column, and the column keys in the top row. The numbers of the rows and columns are related to the way the structure is displayed on a particular carrier. For example, it is possible to remove the left column and the top row from the same table, leaving it without keys.

Here, an attentive reader may accuse us of the different uses of the concept element when considering examples. Indeed, then we understand the element row (or column), the element lies at their intersection. In fact, a table of rows , a table of columns, and a “just” multiplication table look the same only on the book page, but they look different from an access point of view. The difference is already determined by the type of constituent elements of the structure. But not only them. Accordingly, we are talking about different structures, and these three tables will also have to be manipulated differently.