Решение задач

В этой главе мы рассмотрим: In this chapter, you will learn:

• Несколько алгоритмов решения одной и той же вводной задачи Multiple algorithms that solve an introductory problem.

• Как исследовать производительность алгоритма на входных наборах данных размера N. How to consider an algorithm’s performance on problem instances of size N.

• Как посчитать количество основных действий, выполненных при обработке конкретного набора данных. How to count the number of times a key operation is invoked when solving a given problem instance.

• Как определить уровень падения производительности при удвоении входных данных How to determine order of growth as the size of a problem instance doubles.

• Как предсказать сложность алгоритма по времени на основании подсчёта действий, которые он выполнит на входных данных размера N. How to estimate time complexity by counting the number of key operations an algorithm executes on a problem instance of size N.

• Как предсказать сложность алгоритма по памяти на основании оценки дополнительной памяти, которая потребуется ему для обработки входных данных размера N. How to estimate space complexity by determining the amount of memory required by an algorithm on a problem instance of size N.

Что ж, начнем! Let’s get started!

Что такое алгоритм?

What Is an Algorithm?

Объяснять алгоритм — это как рассказывать сказку. Каждый алгоритм — это новый волшебный предмет или неожиданный поступок, которые помогают быстро и легко справиться с казавшейся трудной задачей. В этой главе мы рассмотрим несколько решений нетрудной задачи, а потом разберёмся, какой алгоритм эффективнее, и почему. Кроме того, поймём, как изучать быстродействие алгоритма независимо от его реализации — хотя непосредственные данные о работе конкретных реализаций у нас тоже будут. Explaining how an algorithm works is like telling a story. Each algorithm introduces a novel concept or innovation that improves upon ordinary solutions. In this chapter I explore several solutions to a simple problem to explain the factors that affect an algorithm’s performance. Along the way I introduce techniques used to analyze an algorithm’s performance independent of its implementation, though I will always pro‐ vide empirical evidence from actual implementations.

Алгоритм — это пошаговая инструкция решения некоторой задачи, реализованная в виде программы. Программа должна возвращать правильный ответ за предсказуемое время. Изучая алгоритм, мы проверяем и правильность ответа (в том числе на всех допустимых входных данных), и его вычислительную сложность (возможно, есть более эффективные решения задачи). An algorithm is a step-by-step problem-solving method imple‐ mented as a computer program that returns a correct result in a predictable amount of time. The study of algorithms is concerned with both correctness (will this algorithm work for all input?) and performance (is this the most efficient way to solve this problem?).*/

Давайте посмотрим, как процесс решения и анализа задачи проходит в жизни. Скажем, нам нужно найти наибольшее значение в несортированном списке. В левой части иллюстрации 1-1 приведено три набора данных для нашей задачи¹ — каждый набор в виде списка Python. Данные обрабатываются алгоритмом (изображён как цилиндр), который должен выдавать правильный ответ; ответы перечислены в правой части. Как реализован алгоритм решения? Как он себя ведёт на различных входных наборах? Можно ли предсказать время работы? как быстро можно найти наибольшее из миллиона чисел? Let’s walk through an example of a problem-solving method to see what this looks like in practice. What if you wanted to find the largest value in an unordered list? Each Python list in Figure 1-1 is a problem instance, that is, the input processed by an algorithm (shown as a cylinder); the correct answer appears on the right. How is this algorithm implemented? How would it perform on different problem instances? Can you predict the time needed to find the largest value in a list of one million values?

• Иллюстрация 1-1. Обработка алгоритмом различных наборов входных данных

Figure 1-1. Three different problem instances processed by an algorithm

Алгоритм и реализующая его программа должны не только давать правильный ответ, но и завершаться за предсказуемое время. Наша задача уже решена — для неё в Python есть функция max(). Правда, аккуратно исследовать эффективность алгоритма, оперируя произвольными входными данными, нельзя. Имеет смысл тщательно подготовить подходящие наборы данных. An algorithm is more than just a problem-solving method; the program also needs to complete in a predictable amount of time. The built-in Python function max() already solves this problem. Now, it can be hard to predict an algorithm’s perfor‐ mance on problem instances containing random data, so it’s worth identifying prob‐ lem instances that are carefully constructed.

Таблица 1-1 показывает время работы функции max() на двух типах входных данных различных размеров: в одних наборах целые числа в списке идут по возрастанию, в других — по убыванию. На разных компьютерах результаты окажутся разными, но всегда можно проверить неизменность двух вещей: Table 1-1 shows the results of timing max() on two kinds of problem instances of size N: one where the list contains ascending integers and one where the list contains descending integers. While your execution may yield different results in the table, based on the configuration of your computing system, you can verify the following two statements:

• Время вычисления max() на достаточно длинных возрастающих последовательностях всегда больше времени вычисления на таких же, но убывающих. The timing for max() on ascending values is always slower than on descending values once N is large enough.

• Если длина последовательности увеличивается вдесятеро, время вычисления max() на ней тоже увеличивается плюс-минус вдесятеро, как если бы мы каждую проверку делали вручную. As N increases ten-fold in subsequent rows, the corresponding time for max() also appears to increase ten-fold, with some deviation, as is to be expected from live performance trials.

В нашей задаче вычисляется наибольшее значение, а исходная последовательность не меняется. В некоторых других случаях — например в алгоритмах сортировки элементов списка из главы 5 — требуется не вычислить новое значение, а изменить сами введённые данные. В нашей книге N обозначает размер набора входных данных. For this problem, the maximum value is returned, and the input is unchanged. In some cases, the algorithm updates the problem instance directly instead of comput‐ ing a new value—for example, sorting a list of values, as you will see in Chapter 5. In this book, N represents the size of a problem instance.

Таблица 1-1. Запуск функции max() на двух типах наборов входных данных размера N.² Table 1-1. Executing max() on two kinds of problem instances of size N (time in ms)

Замечания о времени работы: When it comes to timing:

• Невозможно с уверенностью предсказать время работы алгоритма на наборе, допустим, из 100 000 элементов (обозначим это время T(100 000)). Для разных языков программирования и на разных компьютерах это время будет разным. You can’t predict in advance the value of T(100,000)—that is, the time required by the algorithm to solve a problem instance of size 100,000—because computing platforms vary, and different programming languages may be used.

• Однако зная T(10 000) предсказать T(100 000) — время работы на десятикратно больших данных — можно, хотя погрешность такого предсказания неизбежна. However, once you empirically determine T(10,000), you can predict T(100,000)—that is, the time to solve a problem instance ten times larger— though the prediction will inevitably be inaccurate to an extent.

Когда придумываешь алгоритм, важнее всего убедиться, что он работает правильно на всех допустимых наборах входных данных. Как сравнивать свойства двух алгоритмов, если они решают одну и ту же задачу? Этим мы, по большей части, займёмся в главе 2. Изучение алгоритма тесно связано с интересными задачами «из настоящей жизни», в которых он требуется. Математическая сторона алгоритма может быть непростой, но мы постараемся каждое отвлечённое понятие связать с таким вопросом жизненной практики. When designing an algorithm, the primary challenge is to ensure it is correct and works for all input. I will spend more time in Chapter 2 explaining how to analyze and compare the behavior of different algorithms that solve the exact same problem. The field of algorithm analysis is tied to the study of interesting, relevant problems that arise in real life. While the mathematics of algorithms can be challenging to understand, I will provide specific examples to always connect the abstract concepts with real-world problems.

Принято думать, что оценить эффективность алгоритма — значит подсчитать, сколько ему потребовалось вычислительных операций. Но как раз это совсем непросто! Центральный процессор компьютера (CPU) исполняет машинные инструкции — арифметически операции (наподобие сложения и умножения), пересылку данных из памяти в регистры процессора, сравнения и т. п. Современные языки программирования бываю как компилируемые (Си или C++), в которых текст программы перед запуском транслируется в машинные инструкции, так и интерпретируемые (Python или Java). Программа на интерпретируемом языке транслируется в промежуточное представление, называемое байт-кодом. Затем программа-интерпретатор, Python, например (в свою очередь сам написанный на Си и откомпилированный) разбирает и выполняет этот байт-код³. При этом некоторые функции, например min() и max(), встроены Python — они написаны на Си, скомпилированы в машинные инструкции и так выполняются. The standard way to judge the efficiency of an algorithm is to count how many com‐ puting operations it requires. But this is exceptionally hard to do! Computers have a central processing unit (CPU) that executes machine instructions that perform mathe‐ matical computations (like add and multiply), assign values to CPU registers, and compare two values with each other. Modern programming languages (like C or C++) are compiled into machine instructions. Other languages (like Python or Java) are compiled into an intermediate byte code representation. The Python interpreter (which is itself a C program) executes the byte code, while built-in functions, such as min() and max(), are implemented in C and ultimately compiled into machine instructions for execution.

Массив всемогущий

The Almighty Array

А не ворона ли тут? -- FrBrGeorge 2021-11-04 13:36:14

Массив — фиксированный набор однотипных значений, занимающий один непрерывный фрагмент оперативной памяти. Это — одна и самых старых и самых надёжных структур данных; если значений больше одного — программисты хранят их в массиве. НА схеме изображён целочисленный массив из восьми элементов. An array stores a collection of N values in a contiguous block of memory. It is one of the oldest and most dependable data structures programmers use to store multiple values. The following image represents an array of eight integers.

В массиве A — восемь ячеек. Каждая ячейка доступна по номеру, например, A[0] — это 31, а A[7] — 5. В массивах можно хранить и строки, и вообще любые объекты сколь угодно сложного типа. The array A has eight values indexed by their location. For example, A[0] = 31, and A[7] = 5. The values in A can be of any type, such as strings or more complicated objects.

Что следует знать про массивы: The following are important things to know about an array:

• Начальный элемент массива A длиной N имеет индекс 0 и обозначается A[0], конечный обозначается A[N-1] и имеет индекс N-1. The first value, A[0], is at index position 0; the last is A[N–1], where N is the size of the array.

• Зная номер i элемента в массиве, можно прочитать оттуда элемент A[i] или записать на место A[i] новое значение. При этом i — это индекс в диапазоне от 0 до N-1. One can read or update an individual location, A[i], based on the index position, i, which is an integer in the range from 0 to N – 1.

• Длина массива всегда известна. В Python и Java её можно задать в процессе работы программы, а в Си — только заранее. Each array has a fixed length. Python and Java allow the programmer to deter‐ mine this length at runtime, while C does not.

• Чтобы изменить длину массива, необходимо выделить память под новый массив нужной длины и скопировать туда все данные из старого. Просто так размер массива уменьшить или увеличить нельзя. An array cannot be extended (or shrunk); instead, you allocate a new array of the desired size and copy old values that should remain.

Несмотря на простоту, массивы — очень гибкий и удобный инструмент организации данных. В Python имеется тип данных list, с которым можно смело работать как с массивом, хотя его возможности куда шире: в list можно хранить объекты разных типов одновременно, а размер его может меняться в процессе работы программы. Despite their simplicity, arrays are an extremely versatile and efficient way to struc‐ ture data. In Python, list objects can be considered an array, even though they are more powerful because they can grow and shrink in size over time.

Посчитать, сколько машинных инструкций выполнилось при работе алгоритма, практически невозможно — начать с того, что современные компьютеры выполняют их миллиардами за секунду! Давайте вместо этого считать, сколько основных действий выполнил алгоритм. Вопрос «сколько действий?» может означать «сколько раз сравнивались два элемента массива» или, к примеру «сколько раз вызывалась некоторая функция». В случае max() нас будет интересовать, сколько раз вызывалась операция сравнения «меньше, чем» (>). Подробнее о правилах подсчёта действий мы поговорим в главе 2. It is nearly impossible to count the total number of executed machine instructions for an algorithm, not to mention that modern day CPUs can execute billions of instruc‐ tions per second! Instead, I will count the number of times a key operation is invoked for each algorithm, which could be “the number of times two values in an array are compared with each other” or “how many times a function is called.” In this discus‐ sion of max(), the key operation is “how many times the less-than (<) operator is invoked.” I will expand on this counting principle in Chapter 2.

Ну что же, настала пора сорвать покров тайны с алгоритма функции max() и понять, что именно определяет её поведение. Now is a good time to lift up the hood on the max() algorithm to see why it behaves the way it does.

Поиск наибольшего значения в произвольной последовательности

Finding the Largest Value in an Arbitrary List

Рассмотрим (неполноценную) реализацию поиска наибольшего значения произвольной последовательности в примере 1-1. Каждый элемент A сравнивается с my_max, и если найдено значение больше, my_max обновляется. Consider the flawed Python implementation in Listing 1-1 that attempts to find the largest value in an arbitrary list containing at least one value by comparing each value in A against my_max, updating my_max as needed when larger values are found.

Пример 1-1. Неполноценная реализация поиска наибольшего значения последовательности Listing 1-1. Flawed implementation to locate largest value in list

   1 def flawed(A):
   2   my_max = 0        #1
   3   for v in A:       #2
   4     if my_max < v:
   5       my_max = v    #3
   6   return my_max

1. Переменная my_max хранит текущее наибольшее значение. Здесь она инициализируется нулём. / my_max is a variable that holds the maximum value; here my_max is initialized to 0. */

2. В цикле for определена переменная v, которая на каждом проходе цикла равна очередному элементу A. Оператор if внутри цикла выполняется для каждого такого v. The for loop defines a variable v that iterates over each element in A. The if statement executes once for each value, v.

3. Переменная my_max обновляется, если v оказалось больше. Update my_max if v is larger.

Главное в нашем решении — операция сравнения двух выражений на меньше (<), которая определяет, меньше ли первое выражение второго. На иллюстрации 1-2 показано, что по мере прохождения переменной v всех значений из A переменная my_max меняется трижды. Функция flawed() определяет наибольшее значение A из шести элементов, вызывая «<» не более шести раз, по одному разу на каждый элемент. Если в наборе данных будет N элементов, flawed() вызовет «<» не более N раз. Central to this solution is the less-than operator (<) that compares two numbers to determine whether a value is smaller than another. In Figure 1-2, as v takes on suc‐ cessive values from A, you can see that my_max is updated three times to determine the largest value in A. flawed() determines the largest value in A, invoking less-than six times, once for each of its values. On a problem instance of size N, flawed() invokes less-than N times.

• Иллюстрация 1-2. Как работает flawed()

Figure 1-2. Visualizing the execution of flawed()

Эта реализация алгоритма содержит ошибку: предполагается, что в A есть хотя бы одно неотрицательное число. Вызов flawed([–5,–3,–11]) вернёт 0 — что неправильно. Часто вместо нуля пытаются использовать «наименьшее возможное число», примерно так: my_max = float('-inf'). Этот подход также небезупречен, потому что для пустого списка A = [] он вернёт -inf, которого там не было. Недочёт надо исправить. This implementation is flawed because it assumes that at least one value in A is greater than 0. Computing flawed([–5,–3,–11]) returns 0, which is incorrect. One com‐ mon fix is to initialize my_max to the smallest possible value, such as my_max = float('-inf'). This approach is still flawed since it would return this value if A is the empty list []. Let’s fix this defect now.

Python-выражение range(x,y) вычисляет последовательность целых чисел от x до y (не включая y). Если x больше, чем y, можно задать убывающую последовательность от x до y, не включая y, с помощью range(x,y,–1). Если сделать список из range(1,7), list(range(1,7)) даст  [1,2,3,4,5,6]. Соответственно, list(range(5,0,–1)) даст [5,4,3,2,1], а если дополнительно задать шаг — приращение последовательности — list(range(1,10,2)) даст [1,3,5,7,9]: разность между соседними элементами будет равна 2.

Подсчёт действий

Counting Key Operations

Первоначальное значение my_max лучше выбрать из элементов A — тогда можно быть уверенным, что вычисленное нами наибольшее значение будет тоже из A. Работающая на всех входных наборах, кроме пустых, а значит — правильная функция largest() приведена в примере 1-2. Здесь мы выбираем в качестве начального значения my_max начальный элемент A, а затем сравниваем его со всем остальными: вдруг там найдётся побольше? Since the largest value must actually be contained in A, the correct largest() func‐ tion in Listing 1-2 selects the first value of A as my_max, checking other values to see if any value is larger.

Listing 1-2. Correct function to find largest value in list Пример 1-2. Правильная функция, которая находит наибольшее значение в списке

   1 def largest(A):
   2   my_max = A[0]                 #1
   3   for idx in range(1, len(A)):  #2
   4     if my_max < A[idx]:
   5       my_max = A[idx]           #3
   6   return my_max

1. Сделаем my_max равным начальному элементу списка (он доступен по индексу 0). Set my_max to the first value in A, found at index position 0.

2. Переменная idx принимает целочисленные значения от 1 до len(A)-1 включительно, не достигая len(A). idx takes on integer values from 1 up to, but not including, len(A).

3. Если в A по индексу idx стоит большее значение, обновить my_max. Update my_max if the value in A at position idx is larger.

Если передать largest() пустой список — largest([]), — в первой же строчке возникнет исключение IndexError — потому что никакого элемента A[0] в списке нет. Встроенная функция max([]) на пустом списке порождает исключение ValueError с пояснением о том, что пустые последовательности не входят в область определения max(). Так программисту проще понять, в чём его ошибка.

В исправленном алгоритме можно уже начинать считать количество действий. Сколько раз вызывалась в нём операция сравнения «<»? Правильно, N-1 раз. Значит, мы не только избежали ошибки, но и улучшили его производительность (по правде говоря, совсем чуть-чуть). Now that we have a correct Python implementation of our algorithm, can you deter‐ mine how many times less-than is invoked in this new algorithm? Right! N – 1 times. We have fixed the flaw in the algorithm and improved its performance (admittedly, by just a tiny bit).

Почему важно считать именно операции сравнения? Это действие, описанное в алгоритме — сравнить два значения. Другие операторы в программе (например, for или while) выбираются в соответствие с возможностями используемого языка программирования и вполне могут отличаться. Подробнее про это мы поговорим в следующей главе, а пока продолжим считать сравнения.⁴ Why is it important to count the uses of less-than? This is the key operation used when comparing two values. All other program statements (such as for or while loops) are arbitrary choices during implementation, based on the program language used. We will expand on this idea in the next chapter, but for now counting key oper‐ ations is sufficient.

Как оценить эффективность алгоритма по схеме?

Models Can Predict Algorithm Performance

Допустим, нам предлагают совсем иной алгоритм решения нашей задачи. На котором из них остановиться? Рассмотрим функцию alternate() из примера 1-3. В ней каждое значение из A сравнивается со всеми остальными, и если выяснится, что оно не меньше, это и есть ответ. Выдаст ли этот алгоритм правильный ответ? И сколько раз в нём выполняется сравнение на входных данных размера N? What if someone shows you a different algorithm for this same problem? How would you determine which one to use? Consider the alternate() algorithm in Listing 1-3 that repeatedly checks each value in A to see if it is larger than or equal to all other values in the same list. Will this algorithm return the correct result? How many times does it invoke less-than on a problem of size N?

Пример 1-3. Другой способ найти наибольшее значение в списке A. Listing 1-3. A different approach to locating largest value in A

   1 def alternate(A):
   2   for v in A:
   3     v_is_largest = True         #1
   4     for x in A:
   5       if v < x:
   6         v_is_largest = False    #2
   7         break
   8     if v_is_largest:
   9       return v                                  #3
  10   return None                                   #4

1. Предположим, что очередное значение v из цикла по A — наибольшее. When iterating over A, assume each value, v, could be the largest.

2. Если v оказывается меньше какого-то другого значения x из A, прекращаем сравнение и запоминаем, что v — не наибольшее If v is smaller than another value, x, stop and record that v is not greatest.

3. Если к концу цикла v_is_largest всё ещё истинно, значит, v — это и есть максимум, можно возвращать это значение. If v_is_largest is true, return v since it is the maximum value in A.

4. До этого места мы доберёмся, только если список пуст. В этом случае вернём специальный объект Python — None. If A is an empty list, return None.

К сожалению, автор демонстрирует тут не только неэффективный алгоритм (что входило в его задачу), но и не самый лучший стиль программирования на Python. Вот менее «шумный» и более соответствующий идеологии Python вариант:

   1 def alternate(A):
   2     for v in A:         #1
   3         for x in A:
   4             if v < x:   #2
   5                 break
   6         else:
   7             return v    #3
   8     return None         #4

-- FrBrGeorge 2021-10-23 09:59:57

Функция alternate() пытается найти такое значение v из A, чтобы никакое другое значение x из A не оказалось больше него. На этот раз сложно предсказать, сколько потребуется операций сравнения, потому что внутренний цикл по x сразу останавливается, как только выясняется, что x больше v, а внешний — как только v оказывается максимумом. работа alternate() показана на иллюстрации 1-3. alternate() attempts to find a value, v, in A such that no other value, x, in A is greater. The implementation uses two nested for loops. This time it’s not so simple to compute how many times less-than is invoked, because the inner for loop over x stops as soon as an x is found that is greater than v. Also, the outer for loop over v stops once the maximum value is found. Figure 1-3 visualizes executing alternate() on our list example.

• Иллюстрация 1-3. Как работает alternate()

Figure 1-3. Visualizing the execution of alternate()

В данном случае было выполнено 14 сравнений. Впрочем, очевидно, что общее количество действий зависит от от того, какие конкретно значения находятся в списке. Что, если бы они шли в другом порядке? Например, так, чтобы для ответа потребовалось как можно меньше действий? Такой набор данных называется лучшим случаем для alternative(). Например, если наибольший из N элементов последовательности стоит в её начале, количество сравнений в точности равно N. Итак: For this problem instance, less-than is invoked 14 times. But you can see that this total count depends on the specific values in the list A. What if the values were in a different order? Can you think of an arrangement of values that requires the least number of less-than invocations? Such a problem instance would be considered a best case for alternate(). For example, if the first value in A is the largest of all N values, then the total number of calls to less-than is always N. To summarize:

Лучший случай Best case

• Набор данных размера N, на котором алгоритм совершает наименьшее количество действий A problem instance of size N that requires the least amount of work performed by an algorithm

Худший случай Worst case

• Набор данных размера N, требующий наибольшего количества действий A problem instance of size N that demands the most amount of work

Попробуем отыскать наихудший вариант входных данных для alternate(), в котором количество проделанных сравнений было бы наибольшим. Очевидно, что максимум должен лежать в конце A, но вдобавок к этому в наихудшем наборе данных все значения в A должны быть упорядочены по возрастанию. Let’s try to identify a worst case problem instance for alternate() that requires the most number of calls to less-than. More than just ensuring that the largest value is the last value in A, in a worst case problem instance for alternate(), the values in A must appear in ascending order.

На иллюстрации 1-4 показан наилучший случай, в котором A = [9 5 2 1 3 4], и наихудший случай, в котором A = [1 2 3 4 5 9]. Figure 1-4 visualizes a best case on the top where p = [9 5 2 1 3 4] and a worst case on the bottom where p = [1 2 3 4 5 9].

• Иллюстрация 1-4. Как работает alternate() в лучшем и худшем случаях

Figure 1-4. Visualizing the execution of alternate() on best and worst cases

В проиллюстрированном лучшем случае функция делает шесть сравнений вида «больше, чем». Если значений всего N, всего сравнений будет N. В худшем случае подсчёт действий слегка сложнее. По иллюстрации 1-4 видно, что шесть элементов, упорядоченные по возрастанию, потребовали 26 сравнений. Немного арифметики, и становится понятно, что для N элементов число сравнений будет равно $$ (N^2+3N-2)/2 $$ ⁵ In the best case, there are six calls to less-than; if there were N values in a best case, then the total number of invocations to less-than would be N. It’s a bit more compli‐ cated for the worst case. In Figure 1-4 you can see there are a total of 26 calls to less- than when the list of N values is in ascending sorted order. With a little bit of mathematics, I can show that for N values, this count will always be (N2 + 3N – 2)/2.

Таблица 1-2. Сравнение работы largest() и alternate() в худших случаях Table 1-2. Comparing largest() with alternate() on worst case problem instances

Пока данных мало, это ещё терпимо. Но если удвоить размер набора данных, количество сравнений у alternate() фактически увеличится вчетверо, а largest() останется далеко позади. Последние два столбца таблицы 1-2 показывают быстродействие обоих алгоритмов на сотне случайно выбранных наихудших наборах данных размером N. Время работы alternate() тоже увеличивается вчетверо. For small problem instances, it doesn’t seem bad, but as the problem instances double in size, the number of less-than invocations for alternate() essentially quadruples, far surpassing the count for largest(). The next two columns in Table 1-2 show the performance of these two implementations on 100 random trials of problem instan‐ ces of size N. The completion time for alternate() quadruples as well.

Здесь измерялось время, потраченное алгоритмом на обработку набора размером N. Представлены данные о самом быстром (потребовавшем меньше всего времени) решении среди всех попыток. Такой подход лучше обычного вычисления среднего времени по всем однотипным наборам данных, потому что в среднее может закрасться измерение, которое оказалось большим не по вине алгоритма.

В книге будут появляться таблицы с подсчётом количества выполненных действий и затраченного времени, наподобие таблицы 1-2, где измерялось количество сравнений на «больше». Строки таких таблиц соответствуют различным объёмам входных данных. Если проглядеть таблицу сверху вниз, становится понятно, как растут показания в каждом столбце по мере удвоения размера данных. Throughout this book, I am going to present tables, like Table 1-2, containing the total number of executions of a key operation (here, the less-than operator) as well as the runtime performance. Each row will represent a different problem instance size, N. Read the table from top to bottom to see how the values in each column change as the problem instance size doubles.

Подсчёт количества сравнений показывает, как работают функции largest() и alternate(). При удвоении N количество сравнений в largest() удваивается, а в alternate() — увеличивается вчетверо. Это поведение вполне стабильно, и несложно предсказать, как оба алгоритма поведут себя на данных большего размера. На иллюстрации 1-5 показано, что количество сравнений в функции alternate() (отмечено по оси Y с левой стороны) довольно точно соответствует её производительности (затраченное время отмечено по оси Y с правой стороны). Counting the number of less-than invocations explains the behaviors of largest() and alternate(). As N doubles, the number of calls to less-than doubles for largest() but quadruples for alternate(). This behavior is consistent and you can use this information to predict the runtime performance of these two algorithms on larger-sized problems. Figure 1-5 plots the count of less-than invocations by alternate() (using the y-axis on the left) against its runtime performance (using the y-axis on the right), showing how directly they correlate with each other.

• Иллюстрация 1-5. Соотношение количества сравнений и времени работы

Figure 1-5. Relationship between the number of less-than operations and runtime performance

Можем себя поздравить: мы только что сделали важный шаг на пути исследования алгоритмов — оценили относительную производительность двух функций путём сравнения количества выполняемых ими действий. Конечно, теперь можно взять обе реализации, снабдить тестами производительности, в которых размер входных данных несколько раз удваивается, и измерить её на практике, как это сделано в примерах к книге. В действительности достаточно того, что оценка схемы алгоритмов неплохо предсказывает их работу, и из оценки следует, что largest() быстрее, чем alternate(). Congratulations! You’ve just performed a key step in algorithmic analysis: judging the relative performance of two algorithms by counting the number of times a key opera‐ tion is performed. You can certainly go and implement both variations (as I did) and measure their respective runtime performance on problem instances that double in size; but it actually isn’t necessary since the model predicts this behavior and confirms that largest() is the more efficient algorithm of the two.

Наша функция largest() и встроенная функция Python max() реализуют один и тот же алгоритм, но, как это видно из таблицы 1-3, largest() работает значительно — раза в четыре — медленнее, чем max(). Дело в том, что Python — интерпретируемый язык программирования: написанная программа транслируется в промежуточное представление, называемое байт-кодом, а при выполнении программы запускается интерпретатор Python, который читает, интерпретирует и выполняет инструкции байт-кода. Встроенные же функции, например, max() — часть самого интерпретатора: пока такая функция обрабатывает объект, не нужно ничего дополнительного интерпретировать. Поэтому встроенные функции всегда быстрее тех, что написаны на Python⁶. Следует заметить, что во всех случаях реализация одного и того же алгоритма должна приводить к одинаковому изменению быстродействия при изменении размера данных — например, при удвоении N время работы и largest(), и max() тоже удваивается, как в наихудшем, так и в наилучшем случае. largest() and max() are implementations of the same algorithm, but as Table 1-3 shows, largest() is always significantly slower than max(), typically four times slower. The reason is that Python is an interpreted language, which means it is com‐ piled to an intermediate byte code that is executed by a Python interpreter. Built-in functions, such as max(), will always outperform Python code written for the same purpose because the built-in function is implemented within the interpreter. What you should observe is that in all cases, as N doubles, the corresponding performance of largest() and max()—for both best case and worst case—also doubles.

В таблице 1-3 показано, что время, которое тратится на работу с данными при увеличении их размера, вполне предсказуемо. Если знать, сколько времени потратили largest() и max() на наборе длиной N, можно вычислить время, которое они затратят, если увеличить этот надор вдвое. Table 1-3 shows it is possible to predict the time required to solve problem instances of increasing size. Once you know the runtime performance of largest() or max() on a best or worst case problem instance of size N, you can predict that the runtime performance will double as N doubles.

Таблица 1-3. Быстродействие largest() и max() в лучшем и худшем случаях. Table 1-3. Performance of largest() and max() on best and worst cases

Давайте теперь слегка поменяем условия задачи — так она станет поинтереснее. Now let’s change the problem slightly to make it more interesting.

Поиск двух наибольших значений в произвльном списке

Find Two Largest Values in an Arbitrary List

Разработаем алгоритм поиска двух наибольших значений произвольного списка (второе может быть меньше первого или равно ему, но точно не меньше всех остальных). Наверняка же достаточно немного подправить уже имеющийся алгоритм в largest(). Кстати, самое время попробовать справиться с задачей самостоятельно, а потом уже вернуться к нашему примеру! Devise an algorithm that finds the two largest values in an arbitrary list. Perhaps you can modify the existing largest() algorithm with just a few tweaks. Why don’t you take a stab at solving this modified problem and come back here with your solution?

В примере 1-4 показано возможное решение этой задачи. Listing 1-4 contains my solution.

   1 def largest_two(A):
   2   my_max,second = A[:2]                 # 1
   3   if my_max < second:
   4     my_max,second = second,my_max
   5 
   6      for idx in range(2, len(A)):
   7        if my_max < A[idx]:              # 2
   8          my_max,second = A[idx],my_max
   9        elif second < A[idx]:            # 3
  10          second = A[idx]
  11      return (my_max, second)

Пример 1-4. Поиск двух максимумов с помощью отредактированной функции largest_two() Listing 1-4. Find two largest values by tweaking largest() approach

1. Предположим, что my_max и second — первые два значения в списке, если порядок обратный — поменяем их местами. Ensure my_max and second are the first two values from A in descending order.

2. Если A[idx] больше подходит на роль максимума, сделаем my_max равным [idx], а second — равным my_max. If A[idx] is a newly found maximum value, then set my_max to A[idx], and second becomes the old my_max.

3. Если A[idx] больше second, но меньше my_max, обновим только его. If A[idx] is larger than second (but smaller than my_max), only update second.

Функция largest_two() работает похоже на largest(). Сначала предполагается, что my_max и second — это первые два элемента A (порядок проверяется).Затем для всех оставшихся элементов A (сколько их? ну да, N - 2) проверяется очередной A[idx], и если он больше my_max, обновляются обе переменные, а если он больше только second, обновляется только second. largest_two() feels similar to largest(): compute my_max and second to be the first two values in A, properly ordered. Then for each of the remaining values in A (how many? N – 2, right!), if you find an A[idx] larger than my_max, adjust both my_max and second, otherwise check to see whether only second needs updating.

Посчитать количество выполненных сравнений не так-то просто, потому что оно опять зависит от порядка данных в наборе. Counting the number of times less-than is invoked is more complicated because, once again, it depends on the values in the problem instance.

Реже всего largest_two() будет сравнивать значения, если условие оператора if внутри цикла окажется всегда истинным. Например, если в A каждый следующий элемент больше предыдущего, то сравнение их на меньше всегда истинно, так что всего таких сравнений будет N - 2 — плюс ещё одно, которое мы сделали в самом начале функции. Выходит, что в лучшем случае нам потребуется только N - 1 сравнение для поиска двух максимумов. Сравнение в условии при клаузе elif в лучшем случае не используется вообще. largest_two() performs the fewest less-than invocations when the condition of the if statement inside the for loop is true. When A contains values in ascending order, this less-than is always true, so it is invoked N – 2 times; don’t forget to add 1 because of the use of less-than at the beginning of the function. In the best case, therefore, you only need N – 1 invocations of less-than to determine the top two values. The less- than in the elif condition is never used in the best case.

Можно попробовать построить наихудший для largest_two() набор данных — в нём сравнение в условии оператора if внутри цикла всегда должно быть ложным. For largest_two(), can you construct a worst case problem instance? Try it yourself: it happens whenever the less-than in the if condition within the for loop is False.

Наверняка уже понятно, что больше всего сравнений largest_two() делает, когда элементы в A упорядочены по убыванию. Строго говоря, в наихудшем случае должны выполняться оба сравнения на каждом обороте цикла, что даёт нам оценку в $$ 1 + 2 * (N - 2) = 2N - 3 $$ действия. I bet you can see that whenever A contains values in descending order, largest_two() requires the most invocations of less-than. In particular, for the worst case, less-than is used twice each time through the for loop, or 1 + 2 × (N – 2) = 2N – 3 times. Somehow this feels right, doesn’t it? If you need to use less-than N – 1 times to find the largest value in A, perhaps you truly do need an additional N – 2 less-than invocations (leaving out the largest value, of course) to also find the second-largest value.

Таки образом, функция largest_two(): To summarize the behavior of largest_two():

• в лучшем случае тратит $$ N - 1 $$ сравнение на поиск обоих ответов, For best case, it finds both values with N – 1 less-than invocations.

• в худшем случае тратит на аналогичный поиск $$ 2N - 3 $$ сравнения. For worst case, it finds both values with 2N – 3 less-than invocations.

Но вправду ли это и есть «лучший» алгоритм поиска двух наибольших значений в произвольном списке, и наши исследования закончены? Среди имеющихся алгоритмов можно выбирать по нескольким признакам: Are we done? Is this the “best” algorithm to solve the problem of finding the two larg‐ est values in an arbitrary list? We can choose to prefer one algorithm over another based on a number of factors:

Дополнительная память Required extra storage

• Не требуется ли в алгоритме дублировать исходные данные? Does an algorithm need to make a copy of the original problem instance?

Трудоёмкость Programming effort

• Много ли строк в исходной программе? How few lines of code must the programmer write?

Изменение исходных данных Mutable input

• Требуется ли в алгоритме менять непосредственно введённые данные, или их можно не трогать? Does the algorithm modify the input provided by the problem instance in place, or does it leave it alone?

Скороть Speed

• Действительно ли алгоритм работает не хуже других на всех возможных входных наборах данных? Does an algorithm outperform the competition, independent of the provided input?

В примере 5-1 рассмотрим ещё три алгоритма, которые решают ту же самую задачу. Функция sorting_two() создаёт из A новый — отсортированный по убыванию — список, так что первые два его элемента и есть ответ. Функция double_two() находит максимум в A с помощью max(), создаёт копию A, удаляет оттуда этот элемент, и ищет второй ответ тем же самым max() по урезанной копии. Функция mutable_two() находит индекс наибольшего элемента в списке, удаляет его оттуда на время, ищет второй ответ в урезанном списке, после чего вставляет удалённый элемент обратно. Первые два алгоритма нуждаются в дублировании исходных данных, третий изменяет их непосредственно; для всех трёх алгоритмов в наборе данных должно быть больше одного элемента. Let’s investigate three different algorithms to solve this exact same problem, shown in Listing 1-5. sorting_two() creates a new list containing the values in A in descending order, grabs the first two values, and returns them as a tuple. double_two() uses max() to find the maximum value in A, removes it from a copy of A, and then uses max() of that reduced list to find the second largest. mutable_two() finds the location of the largest value in A and removes it from A; then it sets second to the largest value remaining in A before reinserting the my_max value into its original location. The first two algorithms require extra storage, while the third modifies its input: all three only work on problem instances containing more than one value.

   1 def sorting_two(A):
   2   return tuple(sorted(A, reverse=True)[:2])     #1
   3 
   4 def double_two(A):
   5   my_max = max(A)                               #2
   6   copy = list(A)
   7   copy.remove(my_max)                           #3
   8   return (my_max, max(copy))                    #4
   9 
  10 def mutable_two(A):
  11   idx = max(range(len(A)), key=A.__getitem__)   #5
  12   my_max = A[idx]                               #6
  13   del A[idx]
  14   second = max(A)                               #7
  15   A.insert(idx, my_max)                         #8
  16   return (my_max, second)

Пример 1-5. Ещё три способа решить задачу средствами самого Python Listing 1-5. Three different approaches using Python utilities

1. Создать из A новый отсортированный список и вернуть первые два его элемента. Create a new list by sorting A in descending order and return its top two values.

2. Использовать встроенную функцию max() и найти максимум. Use built-in max() function to find largest.

3. Создать дубликат списка A и удалить из него этот максимум. Create a copy of the original A, and remove my_max.

4. Вернуть кортеж из сходного максмума и максимума в урезанной копии. Return a tuple containing my_max and the largest value in copy.

5. Трюк Python, который позволяет найти индекс наибольшего значения, а не само наибольшее значение⁷. This Python trick finds the index location of the maximum value in A, rather than the value itself.

6. Запомнить максимум my_max и удалить его из A. Record my_max value and delete it from A.

7. Найти ещё один max() в усечённом списке. Now find max() of remaining values.

8. Вставить максимальное значение my_max на место. Restore A by inserting my_max to its original location.

Все три способа не используют сравнений явно, потому что задействуют встроенные функции Python. Функции sorting_two() и double_two() копируют исходный список A, а largest_two() — нет; видимо, это необязательно. Вдобавок, сортировать весь список ради всего двух первых элементов тоже кажется излишним. Для обеих функций, задействующих дополнительную память, эту память можно посчитать тем же способом, каким мы считали количество сравнений — и там, и там получится прямо пропорционально N. Третий вариант, mutable_two(), ненадолго изменяет A: удаляет оттуда элемент, а затем добавляет обратно. В программе, откуда была вызвана mutable_two(), возможно, не рассчитывали на то, что A будут изменять⁸. These different approaches do not directly use less-than because they rely on existing Python libraries. Both sorting_two() and double_two() make a copy of the array, A, which seems unnecessary, since largest_two() doesn’t do this. In addition, it seems excessive to sort the entire list just to find the top two largest values. In the same way that I count operations when analyzing runtime performance, I will evaluate the extra storage used by an algorithm—for both of these approaches, the amount of storage is directly proportional to N. The third approach, mutable_two(), briefly updates A by deleting its maximum value, only to add it back later. The caller might be surprised to see that the original list was modified.

Если позволить себе конструкции Python посложнее — ввести специальный класс RecordedItem⁹, можно отследить, сколько операций сравнения на «меньше» потребует любой алгоритм. Из таблицы 1-4 видно, что double_two() делает больше всего сравнений на возрастающей последовательности, а все largest_two() и все остальные — на убывающей. Последний столбец — «Вперемежку» — представляет работу функций на последовательности, в которой на чётных местах элементы возрастают, а на нечётных — убывают: например, для N = 8 перемежающаяся последовательность выглядит как [0,7,2,5,4,3,6,1]. With a bit of Python expertise, I can compute exactly how many times less-than is invoked using a special RecordedItem class.1 Table 1-4 shows that double_two() invokes the most less-than operations when the values are in ascending order, while largest_two() (and others) perform the most less-than operations when the values are in descending order. In the last column, labeled “Alternating,” the 524,288 values are arranged with even numbers in ascending order, alternating with odd numbers in descending order: for N = 8, the input would be [0,7,2,5,4,3,6,1].

Таблица 1-4. Производительность других вариантов решения на нисходящих и восходящих последовательностях. Table 1-4. Performance of different approaches on 524,288 ascending and descending values

Функция tournament_two(), алгоритм которой описан ниже, стабильно показывает наименьшее количество сравнений на любых входных данных. Её логика покажется знакомой поклонникам баскетбола, например. The tournament_two() algorithm I describe next has the fewest number of less-than invocations regardless of input. Basketball fans will find its logic familiar.

Это сноска, она уже переведена 1 The RecordedItem wrapper class overrides the lt() less-than operator to count whenever it (or the gt() greater-than operator) is invoked.

Если некоторый алгоритм решения задачи даёт наихудший результат на некотором наборе данных, другой алгоритм решения той же самой задачи на том же самом наборе данных вовсе не обязан работать так же медленно. У разных подходов — разные слабые места, и надо ещё постараться их найти.

Турнирное дерево

Tournament Algorithm

В состязаниях на вылет выясняется победитель среди нескольких команд. Лучше всего, если количество команд изначально равно какой-нибудь степени двойки, например, 16 или 64. Розыгрыш состоит из нескольких кругов (туров), в каждом из которых все оставшиеся команды разбиваются на пары для игры; каждый проигравший в паре выбывает из соревнований, а остальные переходят на следующий круг. Команда, выигравшая в финале, объявляется победителем. A single-elimination tournament consists of a number of teams competing to be the champion. Ideally, the number of teams is a power of 2, like 16 or 64. The tournament is built from a sequence of rounds where all remaining teams in the tournament are paired up to play a match; match losers are eliminated, while winners advance to the next round. The final team remaining is the tournament champion.

Предположим, нам надо найти максимум в списке p = [3,1,4,1,5,9,2,6] длиной N = 8. На иллюстрации 1-6 показан розыгрыш навылет, в первом туре которого попарно сравниваются на «меньше» восемь значений, и те, что больше, переходят на второй.¹⁰ В туре «Великолепной Восьмёрки» выбывают четыре значения, и остаётся [3,4,9,6], из тура «Чемпионской Четвёрки» в финал выходят [4,9], и в результате победителем становится 9¹¹. Consider the problem instance p = [3,1,4,1,5,9,2,6] with N = 8 values. Figure 1-6 shows the single-elimination tournament whose initial round compares eight neighboring values using less-than; larger values advance in the tournament.2 In the Elite Eight round, four values are eliminated, leaving values [3,4,9,6]. In the Final Four round, values [4,9] advance, and eventually 9 is declared the champion.

• Иллюстрация 1-6. Турнирное дерево с восемью участниками Figure 1-6. A tournament with eight initial values

Для применения турнирного дерева требуется семь сравнений (по одному на игру), и это обнадёживает: как мы уже говорили, это означает, что на поиск максимума в наборе данных размером N требуется N - 1 сравнение. Если запоминать все эти сравнения, нетрудно показать, что второе наибольшее значение находится быстро. In this tournament, there are seven less-than invocations (i.e., one for each match), which should be reassuring, since this means the largest value is found with N – 1 uses of less-than, as we had discussed earlier. If you store each of these N – 1 matches, then you can quickly locate the second-largest value, as I now show.

Переведённная сноска /* /* 2 If a match contains two equal values, then only one of these values advances.

Где может «прячется» второе наибольшее значение, если победителем объявлено 9? Начнём с 4, раз уж оно добралось до финала, и проиграло только там. Однако победитель, 9, участвовал ещё в двух играх, так что надо проверить ещё двух проигравших — 6 из тура «Четвёрки Чемпионов» и 5 из тура «Великолепной Восьмёрки». Получается, что второй ответ — 6. Where can the second-largest value be “hiding” once 9 is declared the champion? Start with 4 as the candidate second-largest value, since this was the value that lost in the Championship round. But the largest value, 9, had two earlier matches, so you must check the other two losing values—value 6 in the Final Four round and value 5 in the Elite Eight round. Thus the second-largest value is 6.

Чтобы выяснить, что 6 — второе наибольшее значение, для длины списка 8 достаточно двух дополнительных сравнений — «4 меньше 6?» и «6 меньше 5?». То, что $$ 8=2^3 $$, а сравнений было $$ 3-1=2 $$ — не совпадение. Действительно, для $$ N=2^K $$ необходимо $$ K - 1 $$ дополнительное сравнение, при этом K оказывается количеством туров в розыгрыше. For eight initial values, you need just 2 additional less-than invocations—(is 4 < 6?) and (is 6 < 5?)—to determine that 6 is the second-largest value. It’s no coincidence that 8 = 23 and you need 3 – 1 = 2 comparisons. It turns out that for N = 2K, you need an additional K – 1 comparisons, where K is the number of rounds.

Для $$ 8=2^3 $$ элементов алгоритму требуется розыгрыш из трёх туров. На иллюстрации 1-7 приведён розыгрыш из пяти туров, соответствующий 32 элементам. Если удвоить количество элементов, потребуется ещё один тур. Иными словами, в туре под номером $$ K $$ может участвовать $$ 2^K $$ элементов. Нужно найти максимум среди 64 элементов? Потребуется шесть туров, потому что $$ 2^6=64 $$ . When there are 8 = 23 initial values, the algorithm constructs a tournament with 3 rounds. Figure 1-7 visualizes a five-round tournament consisting of 32 values. To double the number of values in the tournament, you only need one additional round of matches; in other words, with each new round K, you can add 2K more values. Want to find the largest of 64 values? You only need 6 rounds since 26 = 64.

• Иллюстрация 1-7. Турнирное дерево c 32 участниками Figure 1-7. A tournament with 32 initial values

Чтобы определить, сколько туров потребуется для произвольного N, испльзуеи логарифмическую функцию log() — это обратная к показательной функции, exp(). Для N = 8 элементов на весь розыгрыш требуется три тура, потому что $$ 2^2=8 $$, и стало быть $$ log_(2)8=3 $$. В нашей книге, как и в большинстве задач оценки сложности, используется логарифм с основанием 2 — двоичный¹². To determine the number of rounds for any N, turn to the logarithm function, log(), which is the opposite of the exponent function. With N = 8 initial values, there are 3 rounds required for the tournament, since 23 = 8 and log2(8) = 3. In this book—and traditionally in computer science—the log() operator is in base 2.

Большинство настольных калькуляторов (а заодно — Microsoft Excel) по команде log() вычисляют десятичный логарифм (по основанию 10). Также они имеют команду ln() для вычисления натурального логарифма, основание которого равно константе e (примерно 2.7182818). Чтобы вычислить двоичный логарифм с помощью любой из этих функций, надо поделить результат на логарифм двух: log(N)/log(2).

Если N — степень двойки, например, 64 или 65536, в розыгрыше будет $$ log_2(N) $$ туров, а это значит, что потребуется ещё $$ log_2(N)-1 $$ сравнение. В примере 1-6 приведён алгоритм, который сводит к минимуму количество сравнений за счёт дополнительной памяти, где откладываются результаты этих сравнений. When N is a power of 2—like 64 or 65,536—the number of rounds in a tournament is log(N), which means the number of additional less-than invocations is log(N) – 1. The algorithm implemented in Listing 1-6 minimizes the invocations of less-than by using extra storage to record the results of all matches.

   1 def tournament_two(A):
   2   N = len(A)
   3   winner = [None] * (N-1)           # 1
   4   loser = [None] * (N-1)
   5   prior = [-1] * (N-1)              # 2
   6 
   7      idx = 0
   8      for i in range(0, N, 2):       # 3
   9        if A[i] < A[i+1]:
  10          winner[idx] = A[i+1]
  11          loser[idx] = A[i]
  12        else:
  13          winner[idx] = A[i]
  14          loser[idx] = A[i+1]
  15        idx += 1
  16 
  17      m = 0                          # 4
  18      while idx < N-1:
  19        if winner[m] < winner[m+1]:  # 5
  20          winner[idx] = winner[m+1]
  21          loser[idx] = winner[m]
  22          prior[idx] = m+1
  23        else:
  24          winner[idx] = winner[m]
  25          loser[idx] = winner[m+1]
  26          prior[idx] = m
  27        m += 2                       # 6
  28        idx += 1
  29 
  30      largest = winner[m]
  31      second = loser[m]              # 7
  32      m = prior[m]
  33      while m >= 0:
  34        if second < loser[m]:        # 8
  35          second = loser[m]
  36        m = prior[m]
  37 
  38      return (largest, second)

Пример 1-6. Поиск двух наибольших значений A с помощью турнирного дерева Listing 1-6. Algorithm to find two largest values in A using tournament

1. В этих списках мы станем хранить индексы победителей и проигравших в игре, которых будет N - 1. These arrays store the winners and losers of match idx; there will be N – 1 of them in the tournament.

2. Когда значение в позиции m проходит на очередной тур, в prior[m] записывается позиция этого значения в предыдущем туре. Для первого тура такой информации нет, поэтому в начале этого списка хранится -1 в количестве N - 1 штук. When a value advances in match m, prior[m] records earlier match, or –1 when it was initial match.

3. Первый тур состоит из N/2 игр, то есть требует N/2 сравнений на «меньше» в парах «победитель - проигравший». Initialize the first N/2 winner/loser pairs using N/2 invocations of less-than. These represent the matches in the lowest round.

4. Игры победителей во всех следующих турах с записью позиции выигравшего в каждой игре. Pair up winners to find a new winner, and record prior match index.

5. Еще N/2 - 1 сравнение. An additional N/2 – 1 invocations of less-than are needed.

6. Увеличим m на 2 — это игра двух следующих победителей. Когда idx достигнет N - 1, в winner[m] окажется наибольшее значение. Advance m by 2 to find next pair of winners. When idx reaches N – 1, winner[m] is largest.

7. Первый кандидат на второе место, надо ещё проверить остальных проигравших чемпиону, возможно, они больше подходят для второго места. Initial candidate for second largest, but must check all others that lost to largest to find actual second largest.

8. Не больше $$ log_2(N)-1 $$ дополнительных сравнений на «меньше». No more than log(N) – 1 additional invocations of less-than.

Иллюстрация 1-8 показывает работу нашего алгоритма. Начальный шаг превращает N значений исходного списка A в N/2 значений в winners и в losers; на иллюстрации 1-6 это четыре пары. На следующем шаге с каждым проходом цикла while победитель и проигравший в очередной игре под номером idx (они находятся на соседних позициях m и m+1) помещаются, соответственно, в winner[idx] и loser[idx]. В prior[idx] мы записываем предыдущую позицию выигравшего, с которой он попал в эту игру (обозначено стрелкой справа налево). После трёх шагов мы имеем всю информацию о розыгрыше, и алгоритм проверяет всех проигравших в играх с чемпионом — последовательность, которую можно проследить по стрелкам от чемпиона назад. Второе наибольшее значение можно найти всего двумя сравнениями, что больше — начальный кандидат (найденный в loser[6]), loser[5] или loser[2]. Figure 1-8 shows the execution of this algorithm. After the initialization step, the N values from the original array, A, are separated into N/2 winners and losers; in the example from Figure 1-6, there are four pairs. During each advance step in the while loop, the winner/loser of two consecutive matches, m and m+1, are placed in win ner[idx] and loser[idx] respectively; prior[idx] records the prior match from which the winner came (as drawn by an arrow from right to left). After three steps, all match information is stored, and then the algorithm inspects the losers of all prior matches for the winner. You can visualize this by following the arrows backward until they stop. You can see that the candidate second-largest value is found in loser[6]: with just two less-than invocations with loser[5] and loser[2], it determines which one is largest.

Итак, мы описали алгоритм поиска двух наибольших элементов A, которому нужно всего $$ N-1+log_2(N)-1=N+log_2(N)-2 $$ сравнения на «меньше» для любого N, равного степени двойки. А насколько практична функция tournament_two()? Работает ли она быстрее, чем largest_two()? Если считать только сравнения элементов на меньше, tournament_two() должна быть быстрее. На наборе данных длиной N = 65536 функция largest_two() выполняет 131069 сравнений, а tournament_two() — только 65536 + 16 - 2 = 65550, то есть примерно половину. Но история на этом не кончается. I have just sketched an algorithm to compute the largest and second-largest value in A using just N – 1 + log(N) – 1 = N + log(N) – 2 less-than invocations for any N that is a power of 2. Is tournament_two() practical? Will it outperform largest_two()? If you only count the number of times less-than is invoked, tournament_two() should be faster. largest_two() requires 131,069 less-than operations on problems of size N = 65,536, while tournament_two() only requires 65,536 + 16 – 2 = 65,550, just about half. But there is more to this story.

• Иллюстрация 1-8. Пошаговое выполнение алгоритма с использованием турнирного дерева Figure 1-8. Step-by-step execution of tournament algorithm

В очередной раз хочу заметить, что автор вновь либо демонстрирует невысокий уровень знания Python, либо сознательно избегает рекомендованных в данном случае специфических для Python конструкций, проявляя при этом необъяснимую склонность к путаным и «зашумлённым» реализациям алгоритма. Всё это снижает ценность книги. Отложим разбор авторских прегрешений и рассмотрим более, на мой взгляд, прозрачную, в три раза более короткую и оправданно более быструю (с сохранением того же порядка сложности) реализацию этого алгоритма.

Заведём список season, в который будем добавлять участников всех туров розыгрыша. Фактически это очередь всех игр, в которой каждая пара значений соответствует участникам одной игры в порядке их проведения — от самой первой до финала. Порядок проведения первого тура нам известен — это сам список A, так что вначале season — это копия A. После каждой игры будем добавлять победителя в этот список. Под конец первого тура в нём окажется ещё N / 2 значений — это участники второго тура. Будем продолжать до тех пор, пока на каком-то туре не окажется всего двое — это финал — и в конце концов останется единственный победитель. Всего потребуется N - 1 игра. Параллельно в списке winner будем запоминать, кто победил в каждой игре — первый или второй участник (точнее, нулевой или первый).

Для того чтобы узнать, кто же занял второе место, достаточно посмотреть, кого чемпион победил в финале, в полуфинале и т. д., и выбрать лучшего. Для этого посмотрим в список winner. В его конце записано, каким по номеру был победитель в финальной игре (0 или 1). Его соперник по финалу — кандидат на второе место. Этот номер также указывает, в какой из двух игр полуфинала участвовал победитель. Его соперник по полуфинальной игре — ещё один кандидат на второе место. В действительности поскольку после каждой игры мы добавляем в очередь одного участника из двух, позиция «k» участника во второй половине очереди всегда означает, что он выиграл игру с номером «k». Наша задача — проверить по winner, кто в этой игре выиграл, и исследовать проигравшего в качестве очередного кандидата на второе места.

   1 def tournament_two(A):
   2     season, winner, N = A.copy(), [], len(A)    # 1
   3 
   4     for pos in range(0, 2 * (N - 1), 2):        # 2
   5         who = season[pos] < season[pos + 1]     # 3
   6         season.append(season[pos + who])        # 4
   7         winner.append(who)
   8 
   9     second = season[-2 - winner[-1]]            # 5
  10     match = N - 4 + winner[-1]                  # 6
  11     while match >= 0:
  12         loser = match * 2 + not(winner[match])  # 7
  13         second = max(second, season[loser])     # 8
  14         match = match * 2 + winner[match] - N   # 9
  15 
  16     return second, season[-1]

• Иллюстрация 1-8-1. Работа алгоритма с использованием турнирной очереди Figure 1-8. Step-by-step execution of tournament algorithm

Иллюстрация 1-8-1 показывает работу этой функции. Сначала в очереди весь первый тур розыгрыша. Затем победитель каждой игры добавляется в очередь (а его позиция в игре запоминается). Получается законченная турнирная таблица, из которой мы выбираем наибольшего из проигравших победителю (для удобства в левом верхнем углу клетки указано, в какой игре этот участник победил).

Таблица 1-5 показывает, что функция tournament_two() значительно медленнее всех своих соперниц! Достаточно посмотреть, сколько времени у неё уходит на обработку ста случайных наборов данных, размер которых растёт от 1024 до 2097152 элементов. Раз уж мы об этом заговорили, давайте ещё добавим в таблицу производительность функций из пример 1-5. Если программу с примерами запускать на другом компьютере, конкретные результаты получатся другими, но общая закономерность останется. Table 1-5 reveals that tournament_two() is significantly slower than any of its com‐ petitors! Let’s record the total time it takes to solve 100 random problem instances (of size N growing from 1,024 to 2,097,152). While I’m at it, I will include the perfor‐ mance results of the different algorithms from Listing 1-5. Note that if you run the sample code on your computer, your individual results will be different, but the over‐ all trend in each column will remain the same.

Таблица 1-5. Сравнение времени работы в миллисекундах всех четырёх алгоритмов. Table 1-5. Comparing runtime performance (in ms) of all four algorithms

С непривычки таблица 1-5 выглядит как стена чисел. Если запускать наши функции на другом компьютере — с меньшей памятью или менее мощным процессором — стена будет состоять из других чисел, но некоторые закономерности можно последить безотносительно к быстродействию компьютера. В первую очередь — рост чисел в каждой колонке: при удвоении размера входного набора время выполнения увеличивается тоже примерно вдвое. Table 1-5 can be overwhelming to look at, since it just looks like a wall of numbers. If you run these functions on a different computer—perhaps with less memory or a slower CPU—your results might be quite different; however, there are some trends that should reveal themselves no matter on what computer you execute. For the most part, as you read down any column, the time to execute more or less doubles as the problem size doubles.

В таблице можно заметить кое-что неожиданное: к примеру, double_two() поначалу ведёт себя как самое быстрое решение, но с ростом N (после N >  262,144) уступает пальму первенства largest_two(). А хитрая наша tournament_two() оказалась ужасно медленной — она тратит много времени на создание и обработку вспомогательных списков, размер которых даже больше, чем объём входных данных. Она настолько медленно работает, что на самых больших наборах даже не проверяется — это было бы слишком долго. There are some unexpected situations in this table: note that double_two() starts out being the fastest of the five solutions, but eventually (once N > 262,144), larg est_two() becomes the fastest to complete. The clever tournament_two() approach is by far the slowest, simply because it needs to allocate ever-larger storage arrays to be processed. It is so slow, I do not even run it on the largest problem instance because it will take so long.

Чтобы получить представление обо всех этих числах, посмотрим на иллюстрацию 1-9, где в виде графиков представлена зависимость производительность от роста объёма данных. To make sense of these numbers, Figure 1-9 visualizes the runtime trends as the prob‐ lem size instance grows ever larger.

• Иллюстрация 1-9. Сравнение тестов производительности Figure 1-9. Runtime performance comparison

Графики проявляют особенности работы всех пяти алгоритмов: This image reveals more details about the runtime performance of these five approaches:

• Видно, что производительность mutable_two(), double_two() и largest_two() примерно одинакова, но явно отличается от двух других функций. Можно сказать, что эти три функции образуют «семейство»: графики их производительности — прямые линии, предсказать продолжение которых, по-видимому, просто. You can see that the performances of mutable_two(), double_two(), and largest_two() are all more similar to each other than the other two approaches. It’s almost like they are all in the same “family,” all on a straight-line trajectory that appears quite predictable.

• Функция tournament_two() — самая медленная, и её график заметно отличается от прочих. Измерений сделано немного, поэтому до конца не ясно, будет ли график продолжать «задираться кверху», или тоже превратится в конце концов в прямую. tournament_two() is the least efficient, and it noticeably behaves differently from the other approaches. Given that there are so few data points, it is not clear whether it is “curving upward” to greater inefficiencies or whether it also will fol‐ low a straight line.

• Функция sorting_two() явно получше, чем tournament_two(), однако медленнее остальных трех. А её график? Будет ли он и дальше изгибаться кверху — или стремиться к прямой? appears to do better than tournament_two() but is slower than the other three approaches. Will it curve further upward, or eventually straighten out?

Чтобы понять, отчего графики имеют такой вид, надо обратиться к двум важным понятиям, которые определяют сложность, присущую алгоритмам. To understand why these lines are shaped the way they are, you need to learn the two fundamental concepts that explain the inherent complexity of an algorithm.

Сложность по времени и сложность по памяти

Time Complexity and Space Complexity

Сложно посчитать, сколько конкретных машинных инструкций (например, сложений, присваиваний или ветвлений) выполнила некоторая программа: это очень зависит от языка программирования, тем более, что некоторые из них, например Python или Java, требуют интерпретатора для работы. Но если общее число выполненных инструкций посчитать можно, то можно исследовать, как это число зависит от объёма входных данных. Задача оценки сложности по времени — получить некоторую формулу C(N), которая вычисляла бы количество инструкций, выполненных некоторым алгоритмом, как функцию от N — размера набора входных данных. It can be hard to count the number of elementary operations (such as addition, vari‐ able assignment, or control logic), because of the difference in programming lan‐ guages, plus the fact that some languages, such as Java and Python, are executed by an interpreter. But if you could count the total number of elementary operations exe‐ cuted by an algorithm, then you would see that the total number of operations varies based on the size of the problem instance. The goal of time complexity is to come up with a function C(N) that counts the number of elementary operations performed by an algorithm as a function of N, the size of a problem instance.

Предположим, выполнение одной машинной инструкции центральныи процессором некоторого компьютера требует фиксированного времени t. Тогда время T, затраченное на работу алгоритма на этом компьютере, можно выразить как $$ T(N)=t*C(N) $$. Пример 1-7 подтверждает догадку о том, что самое важное — это структура программы. Можно в точности почитать, сколько потребуется сложений видя ct = ct + 1 для работы функций f0(), f1(), f2() и f3() на входных данных размера N. Assuming that each elementary operation takes a fixed amount of time, t, based on the CPU executing the operation, I can model the time to perform the algorithm as T(N) = t × C(N). Listing 1-7 confirms the insight that the structure of a program is critical. For functions f0, f1, f2, and f3, you can exactly compute how many times each one executes the operation ct = ct + 1 based on the input size, N. Table 1-6 contains the counts for a few values of N.

def f0(N):       def f1(N):           def f2(N):              def f3(N):
  ct = 0           ct = 0               ct = 0                  ct = 0
  ct = ct + 1      for i in range(N):   for i in range(N):      for i in range(N):
  ct = ct + 1        ct = ct + 1          ct = ct + 1             for j in range(N):
  return ct        return ct              ct = ct + 1               ct = ct + 1
                                          ct = ct + 1           return ct
                                          ct = ct + 1
                                          ct = ct + 1
                                          ct = ct + 1
                                          ct = ct + 1
                                        return ct

Пример 1-7. Четыре различные функции с разной вычислительной сложностью Listing 1-7. Four different functions with different performance profiles

Функция f0() всегда выполняет одно и то же количество действий, независимо от N. Количество действий в f2() всегда в семь раз больше, чем в f1(); при удвоении N обе эти функции выполняют в два раза больше действий. В отличие от них, количество действий, выполняемых f3() растёт гораздо быстрее. Мы такое уже видели: N удваивается, сложность f3(N) вырастает в четыре раза. Получается, что f1() и f2() больше похожи друг на друга, чем на f3(). В следующей главе мы обсуди важную роль, которую играют циклы и вложенные циклы при оценке сложности алгоритма. The count for f0 is always the same, independent of N. The count for f2 is always seven times greater than f1, and both of them double in size as N doubles. In con‐ trast, the count for f3 increases far more rapidly; as you have seen before, as N dou‐ bles, the count for f3(N) quadruples. Here, f1 and f2 are more similar to each other than they are to f3. In the next chapter, we will explain the importance of for loops and nested for loops when evaluating an algorithm’s performance.

Таблица 1-6. Количество действий в различных функциях Table 1-6. Counting operations in four different functions

Когда мы исследуем алгоритм, важно установить его сложность по памяти — посчитать, сколько дополнительной памяти требуется на обработку входных данных размера N. Под «памятью» может подразумеваться занимаемое место в файловой системе или объём оперативной памяти, который требуется для работы. Функция largest_two() — потребляет меньше всего памяти: в ней определено всего три переменных — my_max, second и переменная цикла idx. Каким бы ни был объём входных данных, размер дополнительной памяти не меняется. Следовательно, сложность по памяти не зависит от размера входных данных, то есть является константой. Так же ведёт себя и функция mutable_two(). А вот tournament_two() заводит аж три дополнительных списка размера N-1 — winner, loser и prior. Так что при увеличении N объём дополнительной памяти увеличивается прямо пропорционально объёму входных данных.¹³ Необходимость создавать турнирную таблицу делает работу tournament_two() заметно медленнее по сравнению с largest_two(). Ещё две функции — double_two() и sorting_two() — дублируют входные данные (список A), так что их потребление памяти скорее похоже на tournament_two(), чем на largest_two(). В нашей книге мы будем исследовать и сложность по времени, и сложность по памяти каждого алгоритма. When evaluating an algorithm, we also have to consider space complexity, which accounts for extra memory required by an algorithm based on the size, N, of a prob‐ lem instance. Memory is a generic term for data stored in the file system or the RAM of a computer. largest_two() has minimal space requirements: it uses two variables, my_max and second, and an iterator variable, idx. No matter the size of the problem instance, its extra space never changes. This means the space complexity is independ‐ ent of the size of the problem instance, or constant; mutable_two() has similar behav‐ ior. In contrast, tournament_two() allocated three arrays—winner, loser, and prior —all of size N – 1. As N increases, the total extra storage increases in a manner that is directly proportional to the size of the problem instance.3 Building the tournament structure is going to slow tournament_two() down, when compared against larg est_two(). Both double_two() and sorting_two() make a copy of the input, A, which means their storage usage is much more like tournament_two() than larg est_two(). Throughout this book, I will evaluate both the time complexity and space complexity of each algorithm.

Если ещё раз посмотреть на таблицу 1-5, можно заметить, что числа в столбце largest_two с каждой строкой становятся примерно в два раза больше; мы уже подчёркивали, что столбцы double_two и mutable_two устроены в целом так же. Значит, время работы этих алгоритмов прямо пропорционально объёму входных данных, который тоже удваивается на каждой строке. Это важное свойство, ибо эти функции быстрее, чем sorting_two(), а у неё и график быстродействия выглядит по-другому — менее эффективным. Самая медленная — tournament_two(), скорость её работы падает настолько быстрее, чем вдвое, что под конец, на самых больших наборах, мы её даже не запускали.

If you review Table 1-5, you can see that the timing results for the column largest_two more or less double in subsequent rows; columns double_two and mutable_two behave similarly, as I have already observed. This means that the total time appears to be directly proportional to the size of the problem instance, which is doubling in subsequent rows. This is an important observation, since these functions are more efficient than sorting_two(), which appears to follow a different, less- efficient trajectory. tournament_two() is still the least efficient, with a runtime per‐ formance that more than doubles, growing so rapidly that I don’t bother executing it for large problem instances.

С научной точки зрения нельзя просто заявить, что графики производительности largest_two() и mutable_two() «похожи». Нужно формальное теоретическое обоснование и способ фиксации этого утверждения. В следующей главе мы познакомимся с математически инструментарием, который необходим для грамотного исследования производительности алгоритмов. As a computer scientist, I cannot just proclaim that the performance curves of largest_two() and mutable_two() “look the same.” I need to rely on a formal theory and notation to capture this idea. In the next chapter, I will present the mathematical tools necessary to analyze algorithm behavior properly.

Заключение

Summary

В этой главе мы увидели целый спектр хороших и разных алгоритмов. Научились предсказывать производительность алгоритма на входных данных размера N путём подсчёта количества выполненных действий. Также мы посмотрели, как померить производительность конкретной реализации алгоритма опытным путём. В обоих случаях оказалось возможным определить, с какой скоростью падает производительность алгоритма при удвоении объёма N входных данных. This chapter provided an introduction to the rich and diverse field of algorithms. I showed how to model the performance of an algorithm on a problem instance of size N by counting the number of key operations it performs. You can also empirically evaluate the runtime performance of the implementation of an algorithm. In both cases, you can determine the order of growth of the algorithm as the problem instance size N doubles.

Переведённая сноска /* /* 3 That is, storage in addition to the data encoding the problem instance, which is not counted as part of the space complexity of any algorithm.

Мы ввели несколько важных понятий, в частности: I introduced several key concepts, including:

• Сложность по времени оценивается подсчётом количества основных действий алгоритма на наборе входных данных размера N./* Time complexity as estimated by counting the number of key operations executed by an algorithm on a problem instance of size N. */

• Сложность по памяти оценивается измерением дополнительного объёма памяти, который потребуется алгоритму для обработки набора входных данных размера N. Space complexity as estimated by the amount of memory required when an algo‐ rithm executes on a problem instance of size N.

В следующей главе мы рассмотрим математический инструментарий асимптотического анализа и на этом завершим обзор методов формального исследования алгоритмов. In the next chapter, I will introduce the mathematical tools of asymptotic analysis that will complete my explanation of the techniques needed to properly analyze algorithms.

Тренировочные задания

Challenge Exercises

1. Определитель палиндромов Palindrome word detector:

   • Палиндром — слово, буквы которого, расположенные в обратном порядке, дают то же самое слово — например, «казак». Придумать и оформить в виде функции алгоритм, определяющий, что данная строка — это палиндром. Проверить на практике, что написанная функция работает быстрее двух других, предложенных а примере 1-8. A palindrome word reads the same backward as for‐ ward, such as madam. Devise an algorithm that validates whether a word of N characters is a palindrome. Confirm empirically that it outperforms the two alternatives in Listing 1-8:

        1     def is_palindrome1(w):
        2       """Сделаем секцию, содержащую все символы w в обратном порядке
        3       и сравним её с w."""
        4       return w[::-1] == w
        5 
        6     def is_palindrome2(w):
        7       """Если первый и последний символы равны, удалим их.
        8       Если они не равны — вернём False."""
        9       while len(w) > 1:
       10           if w[0] != w[-1]:     # если не равны, вернём False
       11             return False
       12           w = w[1:-1]           # удаляем в цикле первый и последний символ
       13 
       14         return True             # это точно палиндром
     

     • Пример 1-8. Довольно медленные функции-определители палиндрома Listing 1-8. Four different functions with different performance profiles

   • После того, как функция заработает, дополните её: научите определять палиндромы-фразы, в которых пробелы и знаки пунктуации игнорируются, а строчные и прописные буквы не отличаются. Например, вот эта строка — палиндром: «Я не стар, брат Сеня!» Once you have this problem working, modify it to detect palindrome strings with spaces, punctuation, and mixed capitalization. For example, the following string should classify as a palindrome: "A man, a plan, a canal. Panama!"

2. Вычисление медианы за линейное время Linear time median:

   • Есть замечательный алгоритм нахождения медианы в произвольном списке, имеющий линейную сложность (для простоты будем считать, что размер списка нечётен). Изучите исходный текст функций из пример 1-9 и посчитайте количество сравнений с использованием значений упомянутого в этой главе класса RecordedItem. Реализация алгоритма из примера использует переупорядочивание элементов исходного списка. A wonderful algorithm exists that efficiently locates the median value in an arbitrary list (for simplicity, assume size of list is odd). Review the code in Listing 1-9 and count the number of times less-than is invoked, using RecordedItem values as shown in the chapter. This implementation rearranges the arbitrary list as it processes.

   1        import random
   2 
   3        def partition(A, lo, hi, idx):
   4          """Разделение A на две части относительно значения A[idx]."""
   5          if lo == hi: return lo
   6 
   7            A[idx],A[lo] = A[lo],A[idx]    # swap into position
   8            i = lo
   9            j = hi + 1
  10            while True:
  11              while True:
  12                i += 1
  13                if i == hi: break
  14                if A[lo] < A[i]: break
  15 
  16              while True:
  17                j -= 1
  18                if j == lo: break
  19                if A[j] < A[lo]: break
  20 
  21              if i >= j: break
  22              A[i],A[j] = A[j],A[i]
  23 
  24            A[lo],A[j] = A[j],A[lo]
  25            return j
  26 
  27        def linear_median(A):
  28          """
  29          Быстрая реализация поиска медианы в произвольном списке.
  30          Предполагается, что в списке нечётное число элементов.
  31          Обратите внимание на то, что при работе алгоритма
  32          порядок элементов в A меняется.
  33          """
  34          lo = 0
  35          hi = len(A) - 1
  36          mid = hi // 2
  37          while lo < hi:
  38            idx = random.randint(lo, hi)     # select valid index randomly
  39            j = partition(A, lo, hi, idx)
  40 
  41              if j == mid:
  42                return A[j]
  43              if j < mid:
  44                lo = j+1
  45              else:
  46                hi = j-1
  47            return A[lo]

• Пример 1-9. Алгоритм нахождения медианы в неупорядоченном списке за линейное время Listing 1-9. A linear-time algorithm to compute the median value in an unordered list

• Реализуйте другой способ (для него потребуется дополнительная память): отсортируйте список и верните в качестве ответа его средний элемент¹⁴. Сравните быстродействие этого алгоритма с работой linear_median(), составив таблицу тестов производительности. Implement a different approach (which requires extra storage) that creates a sor‐ ted list from the input and selects the middle value. Compare its runtime perfor‐ mance with linear_median() by generating a table of runtime performance.

1. Сортировка подсчётом Counting Sort:

   • Если известно, что некоторый (в остальном произвольный) список A состоит только из целых чисел в диапазоне от 0 до M, такой список можно отсортировать за линейное время, используя дополнительную память размера M. If you know that an arbitrary list, A, only contains nonnegative integers from 0 to M, then the following algorithm will properly sort A using just an extra storage of size M.

   • Хотя в примере 1-10 есть вложенные циклы — for внутри while, — количество присваиваний вида A[pos+idx] = v всё равно ровно N. Докажите это! Listing 1-10 has nested loops—a for loop within a while loop. However, you can demonstrate that A[pos+idx] = v only executes N times.

        1      def counting_sort(A, M):
        2        counts = [0] * M
        3        for v in A:
        4          counts[v] += 1
        5 
        6        pos = 0
        7        v = 0
        8        while pos < len(A):
        9          for idx in range(counts[v]):
       10            A[pos+idx] = v
       11          pos += counts[v]
       12          v += 1
     

     • Пример 1-10. Сортировка подсчётом за линейное время Listing 1-10. A linear-time Counting Sort algorithm

   • Проделайте анализ быстродействия и покажите, что время при удвоении N сортировки N элементов в диапазоне от 0 до M также удваивается. Conduct a performance analysis to demonstrate that the time to sort N integers in the range from 0 to M doubles as the size of N doubles.

   • Внутреннего цикла в counting_sort() можно избежать, если воспользоваться присваиванием секций списка. Если написать что-то вроде список[начало:конец] = [1, 2, 3], то элементы списка в позициях от начала до конца заменятся на 1, 2, 3. Измените counting_sort() и проверьте на практике, что время работы, как и прежде, удваивается при удвоении N, но новая функция работает на 30% быстрее старой. You can eliminate the inner for loop, and improve the performance of this oper‐ ation, using the ability in Python to replace a sublist using sublist[left:right] = [2,3,4]. Make the change and empirically validate that it, too, doubles as N doubles, while yielding a 30% improvement in speed.

2. Исправьте алгоритм с турнирной таблицей так, чтобы он работал для нечётного количества значений. Modify tournament algorithm to work with an odd number of values.

3. Насколько хорошо функция из примера 1-11 находит два наибольших значения в списке A? Will the code in Listing 1-11 correctly locate the two largest values in A?

   •    1      def two_largest_attempt(A):
        2        m1 = max(A[:len(A)//2])
        3        m2 = max(A[len(A)//2:])
        4        if m1 < m2:
        5          return (m2, m1)
        6        return (m1, m2)
     

     • Пример 1-11. Ещё одна попытка найти два наибольших значения в неупорядоченном списке Listing 1-11. Another attempt to try to compute two largest values in unordered list

     При каких условиях функция работает правильно, а при каких — неправильно? Опишите эти условия. Explain the circumstances when this code works correctly and when it fails.