Высокая производительность Delphi (черновик перевода глав 1-2) [Примож Габриэльчич] (fb2) читать постранично, страница - 6

программиста.

In the literature and, of course, on the web, you will see expressions such as O(n), O(n^2), O(1) and similar. This fancy-looking notation hides a really simple story. It tells us how much slower the algorithm will become if we increase the data size by a factor of n.

В литературе и, конечно же, в сети вы увидите такие выражения, как O(n), O(n^2), O(1) и аналогичные. За этими причудливыми обозначениями скрывается действительно простая история. Это говорит нам о том, насколько медленнее станет алгоритм, если мы увеличим размер данных в n раз.

The n^2 notation means "n to the power of two", or n². This notation is frequently used on the internet because it can be written with the standard ASCII characters. This book uses the more readable variant O(n²).

Обозначение n^2 означает «n в степени два», или n². Это обозначение часто используется в Интернете, потому что она может быть написана стандартными символами ASCII. В этой книге используется более читаемый вариант O(n²).

Let's say we have an algorithm with complexity of O(n), which on average takes T seconds to process input data of size N. If we increase the size of the data by a factor of 10 (to 10*N), then the algorithm will (on average) also use 10 times more time (that is, 10*T) to process the data. If we process 1,000 times more data, the program will also run 1,000 times slower.

Допустим, у нас есть алгоритм со сложностью O(n), который в среднем занимает T секунд для обработки входных данных размера N. Если мы увеличим размер данных в 10 раз (до 10*N), то алгоритм (в среднем) также будет использовать в 10 раз больше времени (то есть 10*T) для обработки данных. Если мы обработаем в 1000 раз больше данных, программа также будет работать в 1000 раз медленнее.

If the algorithm complexity is O(n²), increasing the size of the data by a factor of 10 will cause the algorithm to run 10² or 100 times longer. If we want to process 1,000 times more data, then the algorithm will take 1,000² or a million times longer, which is quite a hit. Such algorithms are typically not very useful if we have to process large amounts of data.

Если сложность алгоритма равна O(n²), увеличение размера данных в 10 раз приведет к тому, что алгоритм будет работать в 10² или 100 раз дольше. Если мы хотим обработать в 1 000 раз больше данных, то алгоритм займет в 1 000² или в миллион раз больше времени, что является настоящим ударом. Такие алгоритмы, как правило, не очень полезны, если нам приходится обрабатывать большие объемы данных.

Most of the time, we use the Big O notation to describe how the computation time relates to the input data size. When this is the case, we call the Big O notation time complexity. Nevertheless, sometimes the same notation is used to describe how much storage (memory) the algorithm is using. In that case, we are talking about a space complexity.

Большую часть времени мы используем обозначение Big O, чтобы описать, как время вычисления связано с размером входных данных. Когда это так, мы называем нотацию Big O временно́й сложностью. Тем не менее, иногда та же нотация используется для описания объема хранилища (памяти), используемого алгоритмом. В этом случае мы говорим о пространственной сложности.

You may have noticed that I was using the word average a lot in the last few paragraphs. When talking about the algorithm complexity, we are mostly interested in the average behavior, but sometimes we will also need to know about the worst behavior. We rarely talk about best behavior because users don't really care much if the program is sometimes faster than average.

Возможно, вы заметили, что в последних нескольких абзацах я часто использовал слово «средний». Когда мы говорим о сложности алгоритма, нас в основном интересует среднее поведение, но иногда нам также нужно будет знать о наихудшем поведении. Мы редко говорим о лучшем поведении, потому что пользователям на самом деле все равно, если программа иногда работает быстрее, чем в среднем.

Let's look at an example. The following function checks whether a string parameter value is present in a string list:

Давайте рассмотрим пример. Следующая функция проверяет, присутствует ли значение строкового параметра в списке строк:

function IsPresentInList(strings: TStrings; const value: string): Boolean;

var

   i: Integer;

begin

   Result := False;

   for i := 0 to strings.Count - 1 do

      if SameText(strings[i], value) then

         Exit(True);

end;

What can we tell about this function? The best case is really simple—it will find that the value is equal to strings[0] and it will exit. Great! The best behavior for our function is O(1). That, sadly, doesn't tell us much as that won't happen frequently in practice.

Что мы можем сказать об этой функции? В лучшем случае все действительно просто — она обнаружит, что значение равно strings[0], и завершит работу. Отлично! Наилучшее поведение для нашей функции — O(1). Это, к сожалению, не говорит нам о многом, так как на практике такое случается нечасто.

The worst behavior is also easy to find. If the value is not present in the list, the code will have to scan all of the strings list before deciding that it should return False. In other words, the worst behavior is O(n), if the n represents the number of elements in the list. Incidentally (and without proof), the average behavior for this kind of search is also O(n).

Худшее поведение также легко найти. Если value отсутствует в списке, код должен будет просканировать весь список строк, прежде чем решить, что он должен вернуть значение False. Другими словами, наихудшее поведение — O(n), если n представляет количество элементов в списке. Кстати (и без доказательств),